LeetCode Longest Palindromic Substring
Problem statement
Given a string s, return the longest palindromic substring in s.
Problem statement taken from: https://leetcode.com/problems/longest-palindromic-substring
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)
Explanation
A palindrome is a string that reads the same in both directions. For example, s = 'madam' is a palindrome but s = 'code' is not a palindrome.
Brute force
A brute force solution is to generate all possible substrings and verify if the substring is palindrome or not.
// Generate all substring
for(int i = 0; i < s.size() - 1; i++){
for(int j = i + 1; j < s.size(); j++){
checkIfPalindrome(s, i, j);
}
}Generating all possible substrings using two for loops as shown above will take O(N2) time.
Verifying a string is palindrome or not will take O(N) time. Hence the total time complexity will be O(N3).
Dynamic Programming
The above time complexity can be reduced by using Dynamic programming. Instead of generating all possible substrings, we find if a given substring is a palindrome and expand it across both directions.
Consider a case ababa. We know bab is a palindrome and, ababa will be a palindrome since the left and right letters are the same.
We define a 2D array T(i, j) as follows:
T(i, j) = {
true, if the substring s[i]...s[j] is a palindrome
false, otherwise
}
Hence,
T(i, j) = (T(i + 1, j - 1) and s[i] == s[j]) // the bab and ababa case
Base cases:
// each character in a string is a palindrome.
T(i, i) = true
// palindrome string like 'aa', 'bb' of length 2.
T(i, i + 1) = true if ( s[i] == s[i + 1] )
The time complexity reduced to O(N2) but, the space complexity increased to O(N2) as we need a 2D array to store the result.
Expand around the corner
We can solve this in O(N2) time using only a constant space.
We use a similar concept as mentioned in the above Dynamic Programming section where we expand around the center of the substring and keep updating the maximum length that we have identified so far.
Algorithm
- Assign stringLength = length of string s
- return s if string is empty or stringLength == 0
- Set maxLength = 1.
- Set low, high and start to 0.
- low will act as the left index of a substring.
- high will act as the right index of a substring.
- start will store the index of the longest palindromic substring.
- Loop for i = 1; i < stringLength; i++
// check for even length palindrome substring
- set low = i - 1
- set right = i
- Loop while low >= 0 and high < stringLength && s[low] == s[high]
- if high - low + 1 > maxLength
- maxLength = high - low + 1
- start = low
- decrement low--
- increment high++
// check for odd length palindrome substring
- set low = i - 1
- set right = i + 1
- Loop while low >= 0 and high < stringLength && s[low] == s[high]
- if high - low + 1 > maxLength
- maxLength = high - low + 1
- start = low
- decrement low--
- increment high++
- return s[start : start + maxLength]
C++ solution
class Solution {
public:
string longestPalindrome(string s) {
if(s == '' || s.size() == 0){
return '';
}
int maxLength = 1;
int i, j;
int low, high;
int start = 0;
for(i = 1; i < s.size(); i++){
// check for even length palindrome substring
low = i - 1;
high = i;
while(low >= 0 && high < s.size() && s[low] == s[high]){
if(high - low + 1 > maxLength) {
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
// check for odd length palindrome substring
low = i - 1;
high = i + 1;
while(low >= 0 && high < s.size() && s[low] == s[high]){
if(high - low + 1 > maxLength) {
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
}
return s.substr(start, maxLength);
}
};Golang solution
func longestPalindrome(s string) string {
stringLength := len(s)
if s == '' || stringLength == 0 {
return s
}
maxLength := 1
low, high, start := 0, 0, 0
for i := 1; i < stringLength; i++ {
// check for even length palindrome substring
low = i - 1
high = i
for ;low >= 0 && high < stringLength && s[low] == s[high]; {
if high - low + 1 > maxLength {
start = low
maxLength = high - low + 1
}
low--
high++
}
// check for odd length palindrome substring
low = i - 1
high = i + 1
for ;low >= 0 && high < stringLength && s[low] == s[high]; {
if high - low + 1 > maxLength {
start = low
maxLength = high - low + 1
}
low--
high++
}
}
return s[start:start+maxLength]
}Javascript solution
var longestPalindrome = function(s) {
const stringLength = s.length;
if( s === '' || stringLength == 0 ){
return s;
}
let maxLength = 1;
let low, high;
let start = 0;
for(i = 1; i < stringLength; i++){
// check for even length palindrome substring
low = i - 1;
high = i;
while(low >= 0 && high < stringLength && s[low] === s[high]){
if( high - low + 1 > maxLength ){
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
// check for odd length palindrome substring
low = i - 1;
high = i + 1;
while(low >= 0 && high < stringLength && s[low] === s[high]){
if( high - low + 1 > maxLength ){
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
}
return s.substring(start, start + maxLength);
};Dry Run
Let's dry-run our algorithm to see how the solution works.
s = 'babad'
stringLength = 5
maxLength = 1
low, high, start = 0, 0, 0
Step 1: i = 1, i < 5
// check for even length palindrome substring
low = 0
high = 1
low >= 0 and high < 5 is but s[i] != s[j] as 'b' != 'a'
// check for odd length palindrome substring
low = 0
high = 2
low >= 0 and high < 5 and s[i] == s[j] as 'b' == 'b'
high - low + 1 > maxLength (2 - 0 + 1 > 1)
start = low which is 0
maxLength = high - low + 1 = 3
low-- is -1
high++ is 3
low is -1 so this fails
low >= 0 and high < 5 and s[i] == s[j]
Step 2: i = 2, i < 5
// check for even length palindrome substring
low = 1
high = 2
low >= 0 and high < 5 is but s[i] != s[j] as 'a' != 'b'
// check for odd length palindrome substring
low = 1
high = 3
low >= 0 and high < 5 is and s[i] == s[j] as 'a' == 'a'
high - low + 1 > maxLength (3 - 1 + 1 > 3) false
Step 3: i = 3, i < 5
// check for even length palindrome substring
low = 2
high = 3
low >= 0 and high < 5 is but s[i] != s[j] as 'b' != 'a'
// check for odd length palindrome substring
low = 2
high = 3
low >= 0 and high < 5 is but s[i] != s[j] as 'b' == 'd'
Step 4: i = 4, i < 5
// check for even length palindrome substring
low = 3
high = 4
low >= 0 and high < 5 is but s[i] != s[j] as 'a' != 'd'
// check for odd length palindrome substring
low = 3
high = 5
high is 5 so this fails
low >= 0 and high < 5 is but s[i] != s[j] as 'b' == 'd'
As start is 0 and maxLength is 3
s.substring(start, start + maxLength)
'babad'.substring(0, 3)
=> 'bab'