Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S.

Assumptions

• There exists one unique longest palindromic substring.

• The input S is not null.

Examples Input: "abbc" Output: "bb" Input: "abcbcbd" Output: "bcbcb"

public class Solution {
  public String longestPalindrome(String input) {
    if (input.length() == 0) return input;
    
    int result = 1;
    int start = 0, end = 0;
    for (int i = 0; i < input.length(); i++){
      int oddExpand = expand(input, i, i);
      int evenExpand = expand(input, i , i + 1);
      int maxLen = Math.max(oddExpand, evenExpand);
      if (maxLen > result){
        result = maxLen;
        if(maxLen % 2 == 0){
          start = i - maxLen / 2 + 1;
        } else {
          start = i - maxLen / 2;
        }
        end = i + maxLen / 2;
      }
    }
    return input.substring(start, end + 1);
  }

  private int expand(String input, int left, int right){
    while((left >= 0 && right < input.length()) && input.charAt(left) == input.charAt(right)){
      left--;
      right++;
    }
    return right - left - 1;
  }
}

TC: O(N^2)

SC: O(1)