# 5. Longest Palindromic Substring

## Problem Statement

<br>

Given a string `s`, return *the longest*&#x20;

*palindromic* *substring* in `s`.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "babad"
</strong><strong>Output: "bab"
</strong><strong>Explanation: "aba" is also a valid answer.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "cbbd"
</strong><strong>Output: "bb"
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consist of only digits and English letters.

## Intuition

```
Rather coming from edges 
Expand from the centre

This will eliminate the extra loop 

N^2
```

### Links

<https://leetcode.com/problems/longest-palindromic-substring/description/>

### Video Links

<https://www.youtube.com/watch?v=XYQecbcd6_c&t=275s&ab_channel=NeetCode>

### Approach 1:

```
Scanning from centre
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    string ans = "";
    void expand(string &s , int left ,int right){

        while(left >= 0 &&  right < s.size()){
            if(s[left] != s[right])
                break;
            left--,right++;
        }

        if(ans.size() < right - left )
            ans = s.substr(left + 1 , right - left - 1);
    }

    string longestPalindrome(string s) {

        for(int i = 0 ; i < s.size() ; i++){
            expand(s , i , i);
            expand(s , i , i+1);
        }
        
        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###