5. Longest Palindromic Substring

Problem Statement

Given a string s, return the longest

palindromic substring in s.

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.

Intuition

Rather coming from edges 
Expand from the centre

This will eliminate the extra loop 

N^2

Video Links

Approach 1:

Scanning from centre

C++

class Solution {
public:
    string ans = "";
    void expand(string &s , int left ,int right){

        while(left >= 0 &&  right < s.size()){
            if(s[left] != s[right])
                break;
            left--,right++;
        }

        if(ans.size() < right - left )
            ans = s.substr(left + 1 , right - left - 1);
    }

    string longestPalindrome(string s) {

        for(int i = 0 ; i < s.size() ; i++){
            expand(s , i , i);
            expand(s , i , i+1);
        }
        
        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Problem Statement

Intuition

Links

Video Links

Approach 1:

Approach 2:

Approach 3:

Approach 4:

Similar Problems