5. Longest Palindromic Substring

Problem:

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

5/22/2018 update:
No need to think about after while loop, whether start and end are valid or not. Just update palindrome length within the loop.

class Solution {
    int max = 1;
    int start = 0;
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) 
            return "";
        for (int i = 0; i < s.length() - 1; i++) {
            computePalindrome(s, i, i);
            computePalindrome(s, i, i + 1);
        }
        return s.substring(start, start + max);
    }

    private void computePalindrome(String s, int l, int r) {
        int temp = 0, len = 0;
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            len = r - l + 1;
            temp = l;
            r++;
            l--;
        }
        if (len > max) {
            max = len;
            start = temp;
        }
    }
}

--------------------------------------------------------------------------------------------------------------------------

3/28/2018 update:
An alternative way is to calculate res on every expand. This way sacrifices time for implementation convenience. Should be very careful on start and end when out of while loop. They are not in the right position of palindrome. Need adjustment.

Solution:

class Solution {
    String res = "";
    public String longestPalindrome(String s) {
        if (s == null || s.length() ==0 ) 
            return s;

        for (int i = 0; i < s.length(); i++) {
            helper(s, i, i);
            helper(s, i, i + 1);
        }
        return res;
    }

    private void helper(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        String cur = s.substring(start + 1, end);
        if (cur.length() > res.length()) {
            res = cur;
        }
    }
}

Analysis:
There is no way that one can come up with O(n) solution during the interview. This is a O(n2) solution.

For any palindrome problem, need to consider two cases, odd and even length palindrome. The idea is to iterate thought the array, treat s[i] or s[i], s[i+1] as palindrome center. Then expand to check the current palindrome.

Solution:

 class Solution {  
   public String longestPalindrome(String s) {  
     if (s == null || s.length() == 0) {  
       return null;  
     }  
     int lo = 0, hi = 0, len = 0;  
     for (int i = 0; i < s.length() - 1; i++) {  
       int len1 = expand(s, i, i);  
       int len2 = expand(s, i, i + 1);  
       len = Math.max(len1, len2);  
       if (len > hi - lo + 1) {  
         lo = i - (len - 1)/2;  
         hi = i + len/2;  
       }  
     }  
     return s.substring(lo, hi + 1);  
   }  
   private int expand(String s, int start, int end) {  
     while (start >= 0 && end <= s.length() - 1 && s.charAt(start) == s.charAt(end)) {  
       start--;  
       end++;  
     }  
     return end - start - 1;  
   }  
 }  

Need to be very careful that the final start and end values of expand function are out of range due to the nature of while loop. So the palindrome length is end - start - 1 instead of end  - start + 1.