Doubt on dp leetcodee

#1

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n==1)
return s;

    int dp[n+1][n+1]; //substring index denoting characters with indices

    for(int i=0;i<=n;i++)
        dp[0][i] = dp[1][i] = 1; //since substring with length 0 and 1
								//will always be a palindrome
    
    int resE = 1, resL = 1; //Ending idx and length of the substring
    string res = "";
    for(int i=2;i<=n;i++)
        for(int j=i;j<=n;j++){
            if(dp[i-2][j-1]==1 and s[j-1]==s[j-i])
                dp[i][j] = 1, resE = j, resL = i;
            else
                dp[i][j] = 0;
        }
        
    for(int i=resE-resL;i<resE;i++)
        res += s[i];
    
	return res;
}

};

In ths code for the ques https://leetcode.com/problems/longest-palindromic-substring/
I could not understand
//
(int i=2;i<=n;i++)
for(int j=i;j<=n;j++){
if(dp[i-2][j-1]==1 and s[j-1]==s[j-i])
dp[i][j] = 1, resE = j, resL = i;
else
dp[i][j] = 0;
}
// part of the code

Please help

#2

hello @Somasree

dp[i][j] = is telling whether string of length i which is ending at index j is palindrome or not . ie whether this string -> [j-i+1…j ] is palindrome or not (note -> indexing is one based)

the outer loop (i ) is indicating length .becuase we already marked all 0 and 1 length palindrome we are starting is from 2.

the inner loop ( j ) is indicating the ending index of string (in 1 based indexing).
for example -> 2 length string in 1 based indexing is -> is [1…2] , [2,3]… so on

now for string [j-i+1…j] to be palindrome.

s[j]==s[j-i+1] must be equal , our string s is storing character in 0 based indexing. hence we will compare s[j-1]==s[j-i]

and [j-i+2…j-1] must also be a plaindrome.
so for that we are checking
dp[i-2][j-1]==1 , note i-2 becuase corner two elements are already matched ,so remaining length is i-2. and j-1 becuase it is the ending index of the string.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.