> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/longest-palindromic-substring.md).

# 5. Longest Palindromic Substring

### Description

Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/)
* [Leetcode](https://leetcode.com/problems/longest-palindromic-substring/)
* [ProgramCreek](https://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/)
* [YouTube](https://youtu.be/y2BD4MJqV20)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** "babad"

**Output:** "bab"

**Note:** "aba" is also a valid answer.
{% endtab %}

{% tab title="Example 2" %}
**Input:** "cbbd"

**Output:** "bb"
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n^3)
 * Space complexity : O(1)
 */

class Solution {
    public String longestPalindrome(String s) {
    int maxLen = 0, start = 0, n = s.length();
    for(int i = 0; i < n; i++) {
      for(int j = i+1; j <= n; j++) {
        if((j-i) > maxLen && isPalindrome(s.substring(i, j))) {
          maxLen = j-i;
          start = i;
        }
      }
        if(maxLen == n) break;
    }
    return s.substring(start, start+maxLen);
  }

  public static boolean isPalindrome(String str) {
    int n = str.length();
    for(int i = 0; i < n/2; i++) {
      if(str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;
  }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n^2). Since expanding a palindrome around its center 
 *    could take O(n) time, the overall complexity is O(n^2).
 * Space complexity : O(1).
 */

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(s == null || n == 0) return "";
        int start = 0, end = 0;
        for(int i = 0; i < n; i++) {
            int l1 = expandAroundCenter(s, i, i);
            int l2 = expandAroundCenter(s, i, i+1);
            int len = Math.max(l1, l2);
            if((end-start) < len) {
                start = i - (len-1)/2;
                end = i + (len/2);
            }
        }
        return s.substring(start, end+1);
    }
    
    private int expandAroundCenter(String str, int left, int right) {
        while(left >= 0 && 
              right < str.length() && 
              str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return right-left-1;
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(n^2). This gives us a runtime complexity of O(n^2).
 * Space complexity : O(n^2). It uses O(n^2) space to store the table.
 */

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.isEmpty()) return "";
        char[] sCharArr = s.toCharArray();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        
        int start = 0, maxLen = 1;
        for(int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        for(int i = 0; i < n-1; i++) {
            if(sCharArr[i] == sCharArr[i+1]) {
                dp[i][i+1] = true;
                start = i;
                maxLen = 2;
            }
        }
        
        for(int len = 3; len <= n; len++) {
            for(int i = 0; i < n-len+1; i++) {
                int j = i+len-1;
                if(sCharArr[i] == sCharArr[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    if(len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }

        return s.substring(start, start+maxLen);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Longest substring of vowels - [GFG](https://www.geeksforgeeks.org/longest-substring-vowels)
* Longest Non-palindromic substring - [GFG](https://www.geeksforgeeks.org/longest-non-palindromic-substring/)