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)

Examples

Example 1:

1
2
3

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

Example 2:

1
2

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

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public String longestPalindrome(String s) {
        String ans = "";
        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                // Extract substring s[i...j]
                String sub = s.substring(i, j + 1);
                // Check if substring is palindrome
                if (isPalindrome(sub) && sub.length() > maxLen) {
                    ans = sub;
                    maxLen = sub.length();
                }
            }
        }
        return ans;
    }

    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans: str = ""
        max_len: int = 0
        
        for i in range(len(s)):
            for j in range(i, len(s)):
                # Extract substring s[i...j]
                sub: str = s[i:j + 1]
                # Check if substring is palindrome
                if self.is_palindrome(sub) and len(sub) > max_len:
                    ans = sub
                    max_len = len(sub)
        return ans
    
    def is_palindrome(self, s: str) -> bool:
        l: int = 0
        r: int = len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

Complexity

  • ⏰ Time complexity: O(n^3)
    • Generating all substrings involves two nested loops: O(n^2).
    • For each substring, checking if it’s a palindrome takes O(k) (where k is the length of the substring).
    • Worst-case 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.

1

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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:

b a b a d
b
a
b
a
d
  • i = 0, j = 0, i == j ⇨ dp[i][j] = T
b a b a d
b T
a
b
a
d
  • 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.
b a b a d
b T
a F
b
a
d
  • i = 1, j = 1, b == b ⇨ T
b a b a d
b T
a F T
b
a
d
  • i = 2, j = 0. this is not a base case
b a b a d
b T
a F T
b F
a
d
  • i = 2, j = 1, falls in base case 2.
b a b a d
b T
a F T
b F T
a
d
  • i = 2, j = 2 ⇨ base case 1
b a b a d
b T
a F T
b F T T
a
d
  • 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.
b a b a d
b T
a F T
b F T T
a T
d
  • i = 3, j = 3 ⇨ Base case 1. So, dp[3][3] = True.
b a b a d
b T
a F T
b F T T
a T T
d
  • 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.
b a b a d
b T
a F T
b F T T
a T T
d T
  • i = 4, j = 4 ⇨ Base case. Characters ‘a’ (i) and ‘a’ (j) are the same and i - j (1). So, dp[4][4] = True.
b a b a d
b T
a F T
b F T T
a T T
d T T
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

        String ans = ""; // Store the result
        int maxLen = 0;  // Track maximum palindrome length found so far

        for (int i = 0; i < s.length(); i++) {
            // Odd-length palindrome
            String oddPal = expandAroundCentre(s, i, i);
            if (oddPal.length() > maxLen) {
                ans = oddPal;
                maxLen = oddPal.length();
            }

            // Even-length palindrome
            String evenPal = expandAroundCentre(s, i, i + 1);
            if (evenPal.length() > maxLen) {
                ans = evenPal;
                maxLen = evenPal.length();
            }
        }

        return ans;
    }

    private String expandAroundCentre(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // Return the palindrome substring
        return s.substring(left + 1, right);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand_around_centre(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # Return the palindrome substring
            return s[left + 1:right]

        ans: str = ""
        max_len: int = 0

        for i in range(len(s)):
            # Odd-length palindrome
            odd_pal: str = expand_around_centre(i, i)
            if len(odd_pal) > max_len:
                ans = odd_pal
                max_len = len(odd_pal)

            # Even-length palindrome
            even_pal: str = expand_around_centre(i, i + 1)
            if len(even_pal) > max_len:
                ans = even_pal
                max_len = len(even_pal)

        return ans

Slightly cleaner code

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

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

    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 4 - 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.