Given a string s, return the longest
palindromic
substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
Problem Description
The goal of this problem is to find the longest palindromic substring within a given string s. A palindromic string is a string that reads the same backward as forward, such as ‘radar’ or ‘level’.
To understand the problem, let’s consider what makes up a palindrome:
- A single character is always a palindrome.
- Two characters are a palindrome if they are identical.
- A substring of three or more characters is a palindrome if its first and last characters are the same, and the substring obtained by removing them is also a palindrome.
Given these observations, we need an algorithm that can check for palindromic substrings efficiently and keep track of the longest one found so far.
Intuition
The solution involves Dynamic Programming (DP), an optimization technique that solves complex problems by breaking them into simpler subproblems, storing the solution to each subproblem, and reusing those solutions.
Solution 1: Dynamic Programming The idea is to use a 2D table dp to store whether a substring s[i..j] is a palindrome. We fill this table in a bottom-up manner. For every substring length (from 2 to n), we set dp[i][j] to true if the corresponding substring is a palindrome. Here’s the process:
- For substrings of length 1, each is trivially a palindrome.
- For substrings of length 2, they are palindromes if both characters are the same.
- For longer substrings, we check if the first and last characters are the same and if the substring obtained by removing them (
dp[i+1][j-1]) is a palindrome.
If dp[i][j] is true, we check if it is the longest palindrome so far. If it is, we update the starting index and maximum length of the palindrome.
Solution 2: Enumerating the Palindrome Center An alternative approach is to consider each possible center of the palindrome (which could be a character or between two characters), and expand outwards from the center to see how far the palindrome can be extended. We keep track of the length and starting point of the longest palindrome found during the process.
Implementing the DP Solution The provided Python code uses the dynamic programming approach. Here’s a breakdown of its parts:
- It initializes the
dptable (fin the code) to allTruefor the length 1 substrates, and then iterates backwards over the string. - For each pair
(i, j)it checks ifs[i]matchess[j], then it setsf[i][j]to whatever the value atf[i+1][j-1]is, effectively checking if removing the matching characters still leaves a palindrome. - It keeps track of the start position
kand the max lengthmxof the longest palindrome.
The time complexity of this approach is O(n²) because it examines all possible substrings, making it practical for reasonably short strings.
Solution Approach
The solution to finding the longest palindromic substring employs two main algorithms – Dynamic Programming and Center Expansion. Below is a walkthrough for both.
Dynamic Programming Solution The dynamic programming approach creates a table dp where each entry dp[i][j] records whether the substring s[i..j] is a palindrome.
- Initialize a
nbynmatrixdpwithTruevalues along the diagonal, indicating that all single characters are palindromes. - Iterate over all possible substring lengths
Lstarting from 2 to the length of the input stringn. - For each length
L, iterate over all possible starting indicesifrom which a substring of lengthLcan be obtained. - Use the ending index
j = i+L-1to cover the substring of lengthLstarting at indexi. - Set
dp[i][j]toTrueif and only if the end characters match (s[i] == s[j]) and the internal substrings[i+1..j-1]is a palindrome (dp[i+1][j-1] == True). - Track the starting index and maximum length of the longest palindromic substring found so far.
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True # Base case for one-letter palindrome
mx_len = 1
start = 0
for L in range(2, n + 1):
for i in range(n - L + 1):
j = i + L - 1
if L == 2:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])- The time complexity of this approach is
O(n^2)as we check alln(n-1)/2substrings and updating thedptable takes constant time.
In the code, a 2D list f represents the dp table, where we fill the table starting from the second to last row to the first (i = n - 2 to 0) and from left to right (j = i + 1 to n) within each row. This is because dp[i][j] depends on dp[i + 1][j - 1], which is the next diagonal element below it.
f = [[True] * n for _ in range(n)]
k, mx = 0, 1
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if s[i] != s[j]:
f[i][j] = False
else:
if j - i == 1 or f[i + 1][j - 1]:
f[i][j] = True
if mx < j - i + 1:
k, mx = i, j - i + 1
else:
f[i][j] = FalseHere, the variable k tracks the starting index of the longest palindrome, and mx tracks the length of the longest palindrome.
Center Expansion Solution The center expansion algorithm doesn’t require any additional space except for keeping track of the longest palindrome found.
mx_len = 1
start = 0
for i in range(n):
# Odd Length Palindromes
odd_len = expandFromCenter(s, n, i, i)
if odd_len > mx_len:
mx_len = odd_len
start = i - mx_len // 2
# Even Length Palindromes
even_len = expandFromCenter(s, n, i, i + 1)
if even_len > mx_len:
mx_len = even_len
start = i - (mx_len - 1) // 2
def expandFromCenter(s, n, l, r):
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1Here, the expandFromCenter function checks for the longest palindrome centered at l (for odd lengths) and between l and r (for even lengths), expanding its boundaries outwards as long as the characters match. The lengths of the longest palindromes for both odd and even centers are compared to update the maximum palindrome length mx_len and the starting index start.
The time complexity for this approach is also O(n^2) because each expansion may take O(n) time and there are O(n) potential centers to consider. However, this approach does not use extra space, making it more space-efficient than the dynamic programming approach.
Both approaches are efficient for different scenarios and can be used depending on the space-time trade-off that is more critical for the application at hand.
Example Walkthrough
Let’s consider a small example to illustrate the solution approach, specifically the dynamic programming solution.
Suppose the input string is s = "babad". We are interested in finding the longest palindromic substring.
Following the dynamic programming strategy:
- Initialize the
dptable for a string of length 5 (since"babad"is 5 characters long). Each celldp[i][i]along the diagonal is set toTrue, representing that every single character is a palindrome by itself. Ourdptable initially looks something like this (where0indicatesFalseand diagonals are implicitlyTrue):
| b | a | b | a | d |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
- We check two-character substrings (length
L = 2) for palindromicity. We notice that “ba” is not a palindrome, “ab” is not a palindrome, “ba” again is not a palindrome, but “ad” is not a palindrome either. So, ourdptable does not change. - Now we move on to substrings of length 3. We find “bab” is a palindrome and so is “aba”. The table updates to:
| b | a | b | a | d |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
- We then proceed to substrings of length 4 and 5 but find no longer palindromes.
- The dynamic programming algorithm records the longest palindrome we found, which is “bab” starting at index 0 or “aba” starting at index 1, both with a length of 3.
Here is a snippet of Python code that reflects the process for this example:
s = "babad"
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
mx_len = 1
start = 0
for L in range(2, n + 1):
for i in range(n - L + 1):
j = i + L - 1
if L == 2:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])
if dp[i][j] and L > mx_len:
mx_len = L
start = i
longest_palindrome = s[start:start+mx_len]
print(f'The longest palindrome in the string is: "{longest_palindrome}"')When this code is executed, the longest palindrome “bab” or “aba” (whichever comes first in the updating process) will be printed. The 2D dp matrix serves as a memory that helps avoid recalculating whether a substring is a palindrome, thus saving computational time. Each step relies on the information gathered in the previous steps, making this a bottom-up dynamic programming approach.
Solution Implementation
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size(); // Get the length of the input string
vector<vector<bool>> f(n, vector<bool>(n, true)); // Create a 2D DP table initialized to true
int k = 0, mx = 1; // Variables to track the starting index (k) and the maximum length (mx)
// Iterate through the string in reverse order (from second-to-last character to first)
for (int i = n - 2; ~i; --i) {
// Iterate through each substring starting from i+1 to the end of the string
for (int j = i + 1; j < n; ++j) {
f[i][j] = false; // Initialize the current substring as not a palindrome
// Check if the current characters at positions i and j are equal
if (s[i] == s[j]) {
// Check if the inner substring (from i+1 to j-1) is a palindrome
f[i][j] = f[i + 1][j - 1];
// If the current substring is a palindrome and its length is greater than the current max, update mx and k
if (f[i][j] && mx < j - i + 1) {
mx = j - i + 1; // Update the maximum length of palindrome
k = i; // Update the starting index of the longest palindrome
}
}
}
}
// Return the longest palindrome substring using the stored index k and length mx
return s.substr(k, mx);
}
};class Solution{
public String longestPalindrome(String s) {
int n = s.length(); // Get the length of the input string
boolean[][] f = new boolean[n][n]; // Create a 2D DP table to store whether a substring is a palindrome
// Initialize the DP table with true, assuming all substrings are palindromes
for (var g : f) {
Arrays.fill(g, true); // Fill each row with true
}
int k = 0, mx = 1; // Variables to track the starting index (k) and the maximum length (mx)
// Iterate through the string from second-to-last character to the first
for (int i = n - 2; i >= 0; --i) {
// Iterate through each substring starting from i+1 to the end of the string
for (int j = i + 1; j < n; ++j) {
f[i][j] = false; // Initialize the current substring as not a palindrome
// Check if the current characters at positions i and j are equal
if (s.charAt(i) == s.charAt(j)) {
// If i+1 to j-1 substring is palindrome, then mark i to j as a palindrome
f[i][j] = f[i + 1][j - 1];
// If the current substring is a palindrome and its length is greater than the current max, update mx and k
if (f[i][j] && mx < j - i + 1) {
mx = j - i + 1; // Update the maximum length of palindrome
k = i; // Update the starting index of the longest palindrome
}
}
}
}
// Return the longest palindrome substring using the stored index k and length mx
return s.substring(k, k + mx);
}
}class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s) # Get the length of the input string
f = [[True] * n for _ in range(n)] # Create a 2D list to store whether a substring is a palindrome (initially True)
k, mx = 0, 1 # Variables to track the start index (k) and the length of the longest palindrome (mx)
# Iterate through the string from second-to-last character to the first
for i in range(n - 2, -1, -1):
# Iterate through each substring starting from i+1 to the end of the string
for j in range(i + 1, n):
f[i][j] = False # Initially set the current substring as not a palindrome
# If the current characters at positions i and j are the same, check if the inner substring is a palindrome
if s[i] == s[j]:
f[i][j] = f[i + 1][j - 1] # If inner substring is a palindrome, mark the current substring as a palindrome
# If the current substring is a palindrome and its length is greater than the current max length, update k and mx
if f[i][j] and mx < j - i + 1:
k, mx = i, j - i + 1 # Update the starting index and max length
# Return the longest palindrome substring using the starting index k and the length mx
return s[k : k + mx]
public class Solution {
public string LongestPalindrome(string s) {
int n = s.Length; // Get the length of the input string
bool[,] f = new bool[n, n]; // Create a 2D array to store whether a substring is a palindrome
// Initialize the 2D array to true for all elements, assuming all substrings are palindromes initially
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; ++j) {
f[i, j] = true; // Set all substring values to true initially
}
}
int k = 0, mx = 1; // Variables to track the start index (k) and length of the longest palindrome (mx)
// Start checking substrings from second-to-last character to the first character
for (int i = n - 2; i >= 0; --i) {
// Check substrings starting from the next character to the end of the string
for (int j = i + 1; j < n; ++j) {
f[i, j] = false; // Initially, set the current substring as not a palindrome
// If the current characters at positions i and j are the same
if (s[i] == s[j]) {
// Check if the inner substring (from i+1 to j-1) is also a palindrome
f[i, j] = f[i + 1, j - 1];
// If the current substring is a palindrome and its length is greater than the current max length
if (f[i, j] && mx < j - i + 1) {
mx = j - i + 1; // Update the max length
k = i; // Update the starting index of the longest palindrome
}
}
}
}
// Return the longest palindrome substring using the starting index k and the length mx
return s.Substring(k, mx);
}
}/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
const n = s.length; // Get the length of the input string
// Create a 2D array 'f' to store whether a substring is a palindrome, initialize to true
const f = Array(n)
.fill(0) // Fill with zeros to initialize the array
.map(() => Array(n).fill(true)); // Each row represents a substring of the input string, initially marked as palindrome
let k = 0; // Variable to store the starting index of the longest palindrome substring
let mx = 1; // Variable to store the length of the longest palindrome substring
// Start iterating from the second-to-last character to the first character
for (let i = n - 2; i >= 0; --i) {
// Check all substrings starting from i+1 to the end of the string
for (let j = i + 1; j < n; ++j) {
f[i][j] = false; // Initially mark the substring as not a palindrome
// If characters at positions i and j are equal
if (s[i] === s[j]) {
// Check if the inner substring between i+1 and j-1 is a palindrome
f[i][j] = f[i + 1][j - 1];
// If the current substring is a palindrome and its length is greater than the current max length
if (f[i][j] && mx < j - i + 1) {
mx = j - i + 1; // Update the max length
k = i; // Update the starting index of the longest palindrome
}
}
}
}
// Return the longest palindrome substring using the starting index k and the length mx
return s.slice(k, k + mx); // 'slice' is used to get the substring starting from index k with length mx
};function longestPalindrome(s: string): string {
if (!s || s.length <= 1) { return s }
let longestPalindrome = s.substring(0, 1)
for (let i = 0; i < s.length; i++) {
[expand(s, i, i), expand(s, i, i + 1)].forEach((maybeLongest) => {
if (maybeLongest.length > longestPalindrome.length) {
longestPalindrome = maybeLongest
}
})
}
return longestPalindrome
}
function expand(s: string, begin: number, end: number): string {
while (begin >= 0 && end <= s.length - 1 && s[begin] === s[end]) {
begin--
end++
}
return s.substring(begin + 1, end)
}class Solution {
/**
* @param string $s
* @return string
*/
function longestPalindrome($s) {
// Initialize variables for the start index and the maximum length of palindrome
$start = 0;
$maxLength = 0;
// Iterate through each character of the string
for ($i = 0; $i < strlen($s); $i++) {
// Get the length of palindromes expanding from the current index for odd and even length
$len1 = $this->expandFromCenter($s, $i, $i); // For odd length palindromes
$len2 = $this->expandFromCenter($s, $i, $i + 1); // For even length palindromes
// Determine the larger palindrome length
$len = max($len1, $len2);
// If the found palindrome is longer than the previously recorded one, update the variables
if ($len > $maxLength) {
$start = $i - intval(($len - 1) / 2); // Update start index of the palindrome
$maxLength = $len; // Update maximum length
}
}
// Return the longest palindrome substring found
return substr($s, $start, $maxLength);
}
// Helper function to expand around a center and find the longest palindrome
function expandFromCenter($s, $left, $right) {
// Expand as long as the characters at left and right are equal and within bounds
while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
$left--;
$right++;
}
// Return the length of the palindrome found
return $right - $left - 1;
}
}class Solution {
// Function to find the longest palindromic substring
func longestPalindrome(_ s: String) -> String {
let len = s.count, arr = Array(s) // Convert string to an array of characters for easier manipulation
if len <= 1 { return s } // If the string length is 1 or less, it's already a palindrome, so return it
var lhs = 0, rhs = 0 // Variables to store the left and right boundaries of the longest palindrome found
var dp = Array(repeating: Array(repeating: false, count: len), count: len) // DP table to track if substrings are palindromes
// Iterate through the string to identify potential palindromic substrings
for i in 1..<len {
for j in 0..<i where arr[j] == arr[i] && (dp[j+1][i-1] || i - j <= 2) {
dp[j][i] = true // Mark the substring arr[j...i] as a palindrome
if i - j > rhs - lhs { // If the found palindrome is longer than the current one, update the boundaries
lhs = j // Update the left boundary of the palindrome
rhs = i // Update the right boundary of the palindrome
}
}
}
// Return the longest palindromic substring by slicing the array from lhs to rhs
return String(arr[lhs...rhs])
}
}class Solution {
fun longestPalindrome(s: String): String {
// Step 1: Transform the original string by inserting '#' between characters and adding boundary characters
var str = "$#" // Add a special character to the start of the string
for (i in 0 until s.length) {
str += s[i] // Append each character from the original string
str += "#" // Insert a separator between characters
}
str += "^" // Add a boundary character to the end
// Step 2: Initialize the array to store the palindrome radii
var RL = IntArray(str.length, {0}) // Initialize the array with zeros
var maxr = 0 // Rightmost boundary of the palindrome
var pos = 0 // Center position of the palindrome
var maxlen = 0 // Length of the longest palindrome found
var id = 0 // Index of the center of the longest palindrome
// Step 3: Expand around the center and calculate palindrome radii
for (i in 1 until str.length-1) {
// If we're within the known palindrome bounds, use the mirrored radius for optimization
RL[i] = if (i < maxr) Math.min(RL[2*pos-i], maxr-i) else 1
// Expand the palindrome as long as the characters match
while (str[i-RL[i]] == str[i+RL[i]]) RL[i]++ // Expand radius outwards
// Update the rightmost boundary and position of the current longest palindrome
if (RL[i]+i > maxr) {
maxr = RL[i]+i
pos = i
}
}
// Step 4: Find the largest palindrome radius
for (i in 1 until str.length-1) {
if (RL[i] > maxlen) { // If the current radius is larger than maxlen
maxlen = RL[i] // Update maxlen
id = i // Update the center of the largest palindrome
}
}
// Step 5: Extract the actual palindrome substring from the original string
val start = (id - maxlen) / 2 // Calculate the starting index of the palindrome in the original string
val end = start + maxlen - 1 // Calculate the ending index of the palindrome
return s.substring(start, end) // Return the longest palindromic substring
}
}class Solution {
int lo = 0, maxLen = 0; // Variables to store the starting index and maximum length of the palindrome
// Function to find the longest palindromic substring
String longestPalindrome(String inputTest) {
if (inputTest.isEmpty) {
return ""; // Return empty string if the input is empty
}
if (inputTest.length < 2) {
return inputTest; // Return the string itself if its length is less than 2
}
List items = inputTest.split(''); // Split the input string into a list of characters
for (int i = 0; i < items.length - 1; i++) {
// Expand around the center for both odd-length and even-length palindromes
extendPalindrome(items, i, i); // Odd-length palindrome
extendPalindrome(items, i, i + 1); // Even-length palindrome
}
return inputTest.substring(lo, lo + maxLen); // Return the longest palindromic substring
}
// Helper function to expand around the center and find palindromes
void extendPalindrome(List s, int j, int k) {
// Expand outwards while characters at positions j and k are equal
while (j >= 0 && k < s.length && s[j] == s[k]) {
j--; // Move left pointer
k++; // Move right pointer
}
// Update lo and maxLen if a longer palindrome is found
if (maxLen < k - j - 1) {
lo = j + 1; // Update the starting index of the palindrome
maxLen = k - j - 1; // Update the maximum length of the palindrome
}
}
} func longestPalindrome(s string) string {
// Get the length of the input string
n := len(s)
// Create a 2D slice 'f' for dynamic programming (DP)
// f[i][j] will be true if the substring s[i:j+1] is a palindrome
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
// Initially, all substrings of length 1 are palindromes
for j := range f[i] {
f[i][j] = true
}
}
// Variables to store the starting index and maximum length of the longest palindrome
k, mx := 0, 1
// Traverse the string in reverse order
for i := n - 2; i >= 0; i-- {
// For each substring starting from i, check for palindromes
for j := i + 1; j < n; j++ {
// Set the current substring as not a palindrome
f[i][j] = false
// If the characters at i and j are the same, check if the inner substring is also a palindrome
if s[i] == s[j] {
f[i][j] = f[i+1][j-1]
// If it's a palindrome and it's the longest found so far, update the result
if f[i][j] && mx < j-i+1 {
mx = j - i + 1
k = i
}
}
}
}
// Return the longest palindromic substring
return s[k : k+mx]
}Time and Space Complexity
The time complexity of the code provided is O(n^2), as it includes two nested loops that both iterate over the string length n. Specifically, the outer loop counts down from n-2 to 0, and the inner loop counts up from i+1 to n, resulting in a quadratic number of steps in terms of the length of the input string s.
The space complexity, however, differs from the reference answer. The code creates a 2D list f sized n by n, which is used to store boolean values representing whether a substring is a palindrome or not. This means the space complexity is not O(1), but in fact O(n^2) as well, because storing these values requires a space proportional to the square of the length of the input string s.