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

Links

https://leetcode.com/problems/longest-palindromic-substring/description/

Video Links

https://www.youtube.com/watch?v=XYQecbcd6_c&t=275s&ab_channel=NeetCode

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++

Similar Problems