Given a string find the length of longest palindromic subsequence
belongs to collection: Interview C++ coding problems/challenges | String
All Answers
total answers (1)
belongs to collection: Interview C++ coding problems/challenges | String
total answers (1)
Let,
L(i,j)=length of subsequence from index i to j having length j-i+1
L(i,i)=1 ... base case
It's obvious because each single letter is itself a palindrome and thus every string has palindrome of length 1.
L(i,i) = substring starting from i ending at i, i.e, a single letter<
Now,
L(i,j)=2+L(i+1,j-1) if string[i]=string[j]
L(i,j)=max(L(i+1,j),L(i,j-1)) if string[i]≠string[j]
This is quite obvious : If string[i]=string[j] then it just extends whatever is value for L(i+1,j-1). Else we take the longest possible value so far.
We can actually convert these recursive definitions to our DP matrix.
Initialize DP matrix with 0.
Example with explanation:
Similarly we can carry on iterations for all length and ultimately L[0][n-1] gives the final result
C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer