Longest Palindrome Substring

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"

Brainstorm

• A brute force solution might be to simply iterate through all possible palindrome substrings and get the max.
• We can optimize this by observing that the longer palindrome substrings just build off of the shorter ones.
• Therefore, let's start from the shortest palindrome, a single letter. Let's expand it as much as possible by checking the letters to its sides until it doesn't yield a palindrome.
• Similarly, there may be even length palindromes where the "nucleus" is two letters. We repeat the same process for this.
• In a string of $k$ characters, there are only $2k - 1$ such centers. So, we just have to look at $2k - 1$ palindromes, and determine the longest of these palindromes.

Approach #1: Expanding Around Center

  string longestPalindrome(string s) {
      int maxLen = 1, start = 0;
      // consider every possible palindrome with s[i] as the center 
      for (int i = 1; i < s.length(); i++) {
          // find the maximum possible palindrome with 2 centers/even length
          // e.g. "abba"
          int low1 = i - 1;
          int high1 = i;
          int lengthOfMaxEven = 0;
          while (low1 >= 0 && high1 < s.length() && s[low1] == s[high1]) {
              lengthOfMaxEven = high1 - low1 + 1;
              low1--; 
              high1++;
          }

          // find the maximum possible palindrome with 1 center/odd length
          // e.g. "aba"
          int low2 = i - 1;
          int high2 = i + 1;
          int lengthOfMaxOdd = 0;
          while (low2 >= 0 && high2 < s.length() && s[low2] == s[high2]) {
              lengthOfMaxOdd = high2 - low2 + 1;
              low2--;
              high2++;
          }

          int currMax = max(lengthOfMaxEven, lengthOfMaxOdd);
          if (currMax > maxLen) {
              maxLen = currMax;
              if (currMax == lengthOfMaxEven)
                  start = low1 + 1;
              else if (currMax == lengthOfMaxOdd)
                  start = low2 + 1;
          }
      }

      return s.substr(start, maxLen);
  }

Time complexity: $O(n^2)$

Expanding a palindrome around the center takes $O(n)$ time, and we do this for all $2n - 1$ palindromes. Thus, the overall complexity is $O(n^2)$.

Space complexity: $O(1)$