[leetcode] Longest Palindromic Substring

Problem

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

Solution

1. modeling
2. find an algorithm
3. fast enough? fit in memory?
4. if not, why? figure out!
5. find a way to address the problem
6. iterate until satisfied

• 1. bruteforece =>
     - Time: O(n^3), not fast enough
  • Space: O(1)
• 2. Dynamic Programming: reuse last Palindromic => O(n^2)
     - store if a substring of s from i to j is Palindrome
  • use this if a substring containing (i, j) is Palindrome
  • Time: O(n^2), still...
  • Space: O(n^2), space to store the table

code approach 2

class Solution {
    public boolean[][] m; // to store if s.substring(i, j + 1) is Palindrome
    public String answer;
    
    public String longestPalindrome(String s) {
      	// use array other than sustring, comparing
        char[] chars = s.toCharArray();
        int len = chars.length;
      
      	// initialization
        this.m = new boolean[len][len];
        this.answer = s.substring(0, 1);
        if (len == 1) return s;
        
      	// assign true to memory first (length of substring, 1 and 2)
        for (int i = 0; i < len; i++) 
        {
            m[i][i] = true;
            if (i + 1 < len && chars[i] == chars[i + 1]) 
            {
                m[i][i + 1] = true;
                this.answer = s.substring(i, i + 2);
            }
        }
        
      	// iterate size of a substring from 3
        for (int i = 2; i < len; i++) 
        {
            for (int j = 0; j + i < len; j++) 
            {
              	// if both ends are equal and its substring is Palindrome
                if (chars[j] == chars[j + i] && this.m[j + 1][j + i - 1]) 
                {
                  this.m[j][j + i] = true;
                  // update if current longest String, anwer is shorter than the length of new Palindrome string
                  // i is not a length, but index, so + 1 to calculate the length of the new
                  if (this.answer.length() < i + 1)
                    answer = s.substring(j, j + i + 1);
                }
            }
        }
        
        return this.answer;
    }
    
}

Hide Hint #1
How can we reuse a previously computed palindrome to compute a larger palindrome?

Hide Hint #2
If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?

Hide Hint #3
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

other approach

Approach 4: Expand Around Center

In fact, we could solve it in O(n^2) time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n - 1 such centers.

You might be asking why there are 2n - 1 but not nn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center are between the two 'b's.

Approach 5: Manacher's Algorithm

There is even an O(n) algorithm called Manacher's algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.