# Leetcode 5. Longest Palindromic Substring

# 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`

.

- c is a palindrome substring of length 1.
- Whats the characters on to its left and to right. We see
**b**and we have`bcb`

.`bcb`

is 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`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

- 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).**