3.Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Example 3:
Input: s = "a"
Output: "a"

Example 4:
Input: s = "ac"
Output: "a"

Solution:

This approach is using Dynamic Programming.

class Solution
{
public:
    string longestPalindrome(string s)
    {
        
        if(s==""){return "";}

        int l = s.length();
        bool v[l][l];
        
        for(int i=0;i<l;i++){
            for(int j=0;j<l;j++){
                v[i][j] = false;
            }
        }

        //All string with length 1
        int maxLen = 1, start = 0;
        for (int i = 0; i < s.length(); i++)
        {
            v[i][i] = true;
        }

        //All string with length 2
        for (int i = 0; i < l - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                v[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }

        //All string with length >=3  
        for (int k = 3; k <=l; k++)
        {

            for (int i = 0; i < l - k + 1; i++)
            {
                if (s[i] == s[k + i - 1])
                {
                    if (v[i + 1][k+i - 2])
                    {
                        v[i][k+i-1] = true;
                        start = i;
                        maxLen = k;
                    }
                }
            }
        }

        string res = s.substr(start, maxLen);
        return res;
    }
};

• Time complexity: O(n^2). Two nested traversals are needed.

• Auxiliary Space: O(n^2). Matrix of size n*n is needed to store the dp array.