5. Longest Palindromic Substring| Leetcode solution

 5. Longest Palindromic Substring

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

A string is called a palindrome string if the reverse of that string is the same as the original string.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

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

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

solution:

class Solution {

public:

    string longestPalindrome(string s) {

        int size = s.length();

        if(size == 1)

            return s;

        vector<vector<bool>>dp(size , vector<bool>(size ,false));

        dp[0][0] = true;

        for(int i = 1 ; i < size ; i++)

        {

            for(int j = i ;  j< size ; j++)

            {

                if(i == 1)

                {

                    dp[j][j] = true;

                 if(s[j] == s[j-1])

                 dp[j-1][j] = true;

                }

                if(i == 2)

                {

                     if(s[j] == s[j-2])

                      dp[j-2][j] = true;

                }

                if(s[j] == s[j-i] && dp[j-i+1][j-1] == true)

                {

                    dp[j-i][j] = true;

                }

            }

        }

        int max = 0;

        int i1 =0;

        int i2 = 0;

       for(int i = 0 ; i < size ; i++)

       {

           for(int j = i ; j < size ; j++)

           {

                 if(max < j-i && dp[i][j] == true)

                 {

                       max = j-i;

                       i1 = i;

                       i2 = j ;

                 }

           }

       }

        string result = "";

        for(int i = i1 ; i <= i2 ; i++)

        {

            result += s[i];

        }

        return result;

    }

};