Leetcode 5. Longest Palindromic Substring

Accepted Solution

Problem Statement

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

Test Cases

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 <= 1000
• s consist of only digits and English letters.

Approach

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 abcba.
Consider the middle character c .

1. c is a palindrome substring of length 1.
2. Whats the characters on to its left and to right. We see b and we have bcb . bcb is also palindrome of length 3.
3. Now to the left and right of b, what is the character we are seeing. We see a and we have abcba . abcba is 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.

Algorithm

1. Traverse through the string.
2. 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.
3. Expand from the middle to left and right only when s.charAt(left) = s.charAt(right) .
4. Keep track of the point where the result string starts and the length of the longest palindromic string.
5. 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).

Code

Java Code

LeetCodeTopInterviewQuestions/16_Longest_Palindromic_Substring.java at master ·…