L5 Longest Palindromic Substring

String

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000

Example 1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2:

Input: "cbbd" Output: "bb"

Solution

Expand around the center, either for the length of string is odd or even;

TC : O(n^2) SC: O(1)

public String longestPalindrome(String s){
    if(s == null || s.length() == 0) return "";
    String res = "";
    
    for(int i = 0; i < s.length(); i++){
        String str = search(s,i,i);
        if(str.length() > res.length()){
            res = str;
        }
        str = search(s,i,i+1);
        if(str.length() > res.length()){
            res = str;
        }
    }
    return res;
}
private String search(String s, int left, int right){
    while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
        left--;
        right++;
    }
    return s.subString(left + 1, right);
}

Note:

what left + 1 is for ?

for the example, babad, when we already got the bab, for jumping out the function , the index gonna be -1, that is not what we want. So we need to plus one