educative.io

For basic solution, can we just compare c2 and c3 without c1?

Courses
,
#1

for Longest Palindromic Subsequence, we either return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1); or return Math.max(c1, c2).

The code is below

// case1    
return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1);

// case 2: skip one element either from the beginning or the end
int c1 =  findLPSLengthRecursive(st, startIndex+1, endIndex);
int c2 =  findLPSLengthRecursive(st, startIndex, endIndex-1);
return Math.max(c1, c2);

In Longest Palindromic string, can we do the same? I mean either return case 1 or return case2.

let’s say

 // case 1
if(st.charAt(startIndex) == st.charAt(endIndex)) {
  int remainingLength = endIndex-startIndex-1;
  if(remainingLength == findLPSLengthRecursive(st, startIndex+1, endIndex-1))
    return remainingLength + 2;
}

// case 2: skip one character either from the beginning or the end
int c2 =  findLPSLengthRecursive(st, startIndex+1, endIndex);
int c3 =  findLPSLengthRecursive(st, startIndex, endIndex-1);
return Math.max(c2, c3);

if we can do this, then time complexity is O(2^n) which is better than O(3^n)

1 Like
#2

i also think the same

#3

Yes, we can do this. It would be efficient but overall time complexity will remain the same O(3^n), as in the worst case the following ‘if’ will fail and we still have to make the other two recursive calls:

if(remainingLength == findLPSLengthRecursive(st, startIndex+1, endIndex-1))

“Longest Palindromic Subsequence” is O(2^n) because we don’t have the above ‘if’ condition in it. This all comes down to the following reason (mentioned in ‘Longest Palindromic Substring’):

The only difference is that in a palindromic subsequence characters can be non-adjacent, whereas in a substring all characters should form a palindrome.

Hope this clarifies your question.

1 Like