Longest Palindromic Substring Problem

Problem

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

Incase of conflict, return the substring which occurs first ( with the least starting index ).

Substring of string S: S[i...j] where 0 <= i <= j < len(S)

Example

Example 1:

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

Example 2:

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

Solution

Method 1 - Brute Force

The simple approach is to check each substring whether the substring is a palindrome or not. We can run three loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

Complexity

• ⏰ Time complexity: O(n^3)
• 🧺 Space complexity: O(1)

Method 2 - Dynamic Programming

Let s be the input string, i and j are two indices of the string. Define a 2-dimension array “table” and let dp[i][j] denote whether a substring from j to i is palindrome, and it is filled in bottom up manner.

The value of dp[i][j] is true, if the substring is palindrome, otherwise false.

table[i][j] = true if (table[i+1][j-1] && ( s.charAt(i)==s.charAt(j) ))

Code

Java

public String longestPalindrome(String s) {
	if (s == null || s.length() <= 1) {
		return s;
	}

	int n = s.length();
	boolean[][] dp = new boolean[n][n];

	int maxLen = 1; // atleast longest palindrome will have 1 char
	int start = 0;
	int end = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			// Base cases:
			// - Single character is a palindrome (length 1)
			if (i == j) {
				dp[i][j] = true;
			}
			// - Two adjacent characters are a palindrome (length 2)
			else if (i - j == 1 && s.charAt(i) == s.charAt(j)) {
				dp[i][j] = true;
			} else {
				// Check if the substring between (j + 1) and (i - 1) is a palindrome
				// and the characters at i and j are the same
				dp[i][j] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
			}
			// Update maxLen and start/end if a longer palindrome is found
			if (dp[i][j] && maxLen  <  i - j + 1) {
				maxLen = i - j + 1;
				start = j;
				end = i;
			}
		}
	}

	return s.substring(start, end + 1);;
}

Complexity

• ⏰ Time complexity: O(n^2)
• 🧺 Space complexity: O(n^2)

Dry Run

Consider the string s = "babad" (n = 5). Lets start filling the DP table.

Filling in DP table

For the base case 1, aka i == j, we will have DP table like:

• i = 0, j = 0, i == j ⇨ dp[i][j] = T

• i = 1, j = 0. As i - j == 1, that means adjacent characters, but b != a hence we go to last case. dp[i][j] = F.

• i = 1, j = 1, b == b ⇨ T

• i = 2, j = 0. this is not a base case

• i = 2, j = 1, falls in base case 2.

• i = 2, j = 2 ⇨ base case 1

• i = 3, j = 0 ⇨ not a base case similar to dp[1][0], hence dp[3][0] = F
• i = 3, j = 1 ⇨ Characters ‘b’ (i) and ‘a’ (j) are different, so dp[3][1] is set to False.
• i = 3, j = 2 ⇨ Base case. Characters ‘b’ (i) and ‘b’ (j) are the same and i - j (1). So, dp[3][2] = True.

• i = 3, j = 3 ⇨ Base case 1. So, dp[3][3] = True.

• i = 4, j = 0 ⇨ Not a base case. Similar to previous cases, dp[4][0] = False.
• i = 4, j = 1 ⇨ Not a base case. Characters ’d’ (i) and ‘a’ (j) are different, so dp[4][1] is set to False.
• i = 4, j = 2 ⇨ Not a base case. Characters ’d’ (i) and ‘b’ (j) are different, so dp[4][2] is set to False.
• i = 4, j = 3 ⇨ Base case. Characters ‘a’ (i) and ‘a’ (j) are the same and i - j (1). So, dp[4][3] = True.

• i = 4, j = 4 ⇨ Base case. Characters ‘a’ (i) and ‘a’ (j) are the same and i - j (1). So, dp[4][4] = True.

Finding the Longest Palindrome

Now that the DP table is filled, we need to find the longest palindrome based on the True values.

• We can see that dp[3][2] = True (substring “bab” is a palindrome).
• We also see that dp[1][1] = True (substring “a” is a palindrome, but it’s shorter than “bab”).
• Since dp[3][2] represents a longer palindrome (length 3), we update:
  • maxLen = 3
  • start = 2 (index of ‘b’ in “bab”)
  • end = 4 (index of ‘b’ in “bab” - remember indexing starts from 0)

Method 3 - Generate the Palindromes by expanding from middle 🏆

When we usually check the palindromes, we check it from outward to invward, i.e 2 pointers left and right move towards the centre. What if we start from center and look outward.

For eg. take the string babad. When i = 0, we have b. We cannot expand on left, so b is only palindrome. Lets have i = 1, we get a. Now, we can go both leftwards and rightwards, we get bab as the palindrome now.

So, when we go from point in array, say i, we expand on left and right; So, overall time complexity will be O(n^2).

The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

• Step to generate odd length palindrome: Fix a centre and expand in both directions for longer palindromes.
• Step to generate even length palindrome: Fix two centre ( low and high ) and expand in both directions for longer palindromes.

Code

Java

public String longestPalindrome(String s) {
	if (s == null || s.length() < 1) {
		return "";
	}

    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i++) {
        // odd length palindrome
        String tmp = expandFromMiddle(s, i, i);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }

        // even length palindrome
        tmp = expandFromMiddle(s, i, i + 1);
        if (tmp.length() > longest.length()) {
            longest = tmp;
        }
    }

    return longest;
}

// Given a center, either one letter or two letter,
// Find longest palindrome
public String expandFromMiddle(String s, int begin, int end) {
    while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
        begin--;
        end++;
    }
    return s.substring(begin + 1, end);
}

We can make the code cleaner, by changing expandFromMiddle to return the length, and we create the substring only when needed:

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandFromMiddle(s, i, i);
            int len2 = expandFromMiddle(s, i, i + 1);

            int len = Math.max(len1, len2);

            if (len > (end - start)) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    private static int expandFromMiddle(String s, int left, int right) {

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return right - left - 1;
    }

Complexity

• ⏰ Time complexity: O(n^2)
• 🧺 Space complexity: O(1)

Method 3 - Manacher’s Algorithm

Manacher’s algorithm is much more complicated to figure out, even though it will bring benefit of time complexity of O(n). Here it is: Manachar’s Algorithm - Longest palindromic substring in linear time.