Road to coding interview (Day 3)

Photo by Gabrielle Henderson on Unsplash

What I want to write today is the third question in the list: Longest Palindromic Substring

After many glance, I still have no idea how to solve it. Thus, I tried to look for good solution in discussion. I found the answer given by GraceMeng.

string longestPalindrome(string s) {
    if(s.size() <= 1)
        return s;
    int len = s.size(), ans_start = 0, ans_size = 1;
    bool dp[len][len];
for(int i = 0; i < len; i++)
        dp[i][i] = true;
for(int i = len - 1; i >= 0; i--){
        for(int j = 1; j < len - i; j++){
            int k = i + j;
            if(j == 1)
                dp[i][k] = (s[i] == s[k]);
            else
                dp[i][k] = (s[i] == s[k] && dp[i + 1][k - 1]);
if(dp[i][k] && j + 1 > ans_size){
                ans_start = i;
                ans_size = j + 1;
            }
}
    }
    return s.substr(ans_start, ans_size);
}

Be aware of the boundary in inner loop, len-imake sure tail index k will not out of range (len).