Leetcode 5. Longest Palindromic Substring
Given a string
s, return the longest palindromic substring in
Input: s = "babad"
Explanation: "aba" is also a valid answer.
Input: s = "cbbd"
1 <= s.length <= 1000
sconsist of only digits and English letters.
We are given a string and we need to find the largest substring which is also a palindrome. So what is a palindrome string? A palindrome string is a string which when read from left to right and right to left are the same.
Eg : aba, racecar, a, aa etc.
So we need to find the largest palindromic substring. The simple way will be to consider all the palindromic substring of the input string and store the largest among them. But this approach will be too slow as there are many steps that we are doing repeatedly.
Now let’s have an observation. Suppose we are given a string say
Consider the middle character
- c is a palindrome substring of length 1.
- Whats the characters on to its left and to right. We see b and we have
bcbis also palindrome of length 3.
- Now to the left and right of b, what is the character we are seeing. We see a and we have
abcbais also a palindrome of length 5.
So we can see, from a particular character, we can just check the left char and right char and see if its equal. If equal continue expanding further to the left and right till
s.charAt(left) != s.charAt(right) .So this is the idea what we can apply for the problem. From each and every character of the input string, we can just try to expand from the middle to the left and to the right.
c = palindrome, then
xcx is also palindrome
yxcxy is also palindrome
zyxcxyz is also a palindrome and so on.
Now what is the case with
abba . This is also a palindromic string with length 4. But it doesn’t have a proper middle like
abcba . For this case, we do the same expand from middle idea but we start our expand from
bb . We keep a pointer at
b and the other pointer at other
b and just apply the same expand technique to the left and right.
bb = palindrome, then
xbbx is also palindrome
yxbbxy is also palindrome
zyxbbxyz is also palindrome and so on.
- Traverse through the string.
- Make two function call. One to track odd length palindrome and another for even length palindrome.
fun(s, i, i) -> we have a proper middle part for odd palindrome
fun(s, i, i + 1) -> no proper middle part for even palindrome.
- Expand from the middle to left and right only when
s.charAt(left) = s.charAt(right).
- Keep track of the point where the result string starts and the length of the longest palindromic string.
- Finally return
s.substring(resultStart, resultStart + resultLength).
Time and Space Complexity
Here we are traversing through the string twice at a time. Like normally we are doing a traversal and inside that traversal we are doing the expand from middle operation. So our time complexity will be O(n²) where n = length of the input string.
We are not making use of any extra space, so our space complexity is O(1).