5. Longest Palindromic Substring

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.

Approach

• We use a method of expansion where for a given left and right index we expand left and right and check if the characters are equal
• Two kind of expansion odd where start index is same for both and for even i and i + 1
• Remember - after loop completion we would have reached one one index extra towards either side and also substring includes start and excludes end
• Time: O(n^2) Space: O(1)
• There is one more O(n) way while using Manacher's Algorithm which is designed for this

class Solution {
    public String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = expand(s,i,i);
            String even = expand(s,i,i+1);
            if (longest.length() < odd.length())
                longest = odd;
            if (longest.length() < even.length())
                longest = even;    
        }
        return longest;
    }
 
    public String expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}