# Longest Palindromic Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-palindromic-substring)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindromic-substring
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Deloitte](https://scaleengineer.com/companies/deloitte), [DoorDash](https://scaleengineer.com/companies/doordash), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [EarnIn](https://scaleengineer.com/companies/earnin), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Grab](https://scaleengineer.com/companies/grab), [Huawei](https://scaleengineer.com/companies/huawei), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Mastercard](https://scaleengineer.com/companies/mastercard), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nielsen](https://scaleengineer.com/companies/nielsen), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [Paytm](https://scaleengineer.com/companies/paytm), [Pwc](https://scaleengineer.com/companies/pwc), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [eBay](https://scaleengineer.com/companies/ebay), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Commvault](https://scaleengineer.com/companies/commvault), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Dell](https://scaleengineer.com/companies/dell), [MAQ Software](https://scaleengineer.com/companies/maq-software), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Softwire](https://scaleengineer.com/companies/softwire), [Tesla](https://scaleengineer.com/companies/tesla), [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks), [Turing](https://scaleengineer.com/companies/turing), [Autodesk](https://scaleengineer.com/companies/autodesk), [BlackRock](https://scaleengineer.com/companies/blackrock), [CEDCOSS](https://scaleengineer.com/companies/cedcoss), [Disney](https://scaleengineer.com/companies/disney), [Info Edge](https://scaleengineer.com/companies/info-edge), [LiveRamp](https://scaleengineer.com/companies/liveramp), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [RBC](https://scaleengineer.com/companies/rbc), [Turo](https://scaleengineer.com/companies/turo), [UiPath](https://scaleengineer.com/companies/uipath), [Wayfair](https://scaleengineer.com/companies/wayfair), [Zepto](https://scaleengineer.com/companies/zepto)
---
## Problem
Given a string `s`, return _the longest_ _palindromic_ _substring_ in `s`.

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

# Approaches
## Brute Force
This approach is the most straightforward but also the most inefficient. The core idea is to check every single substring of the input string `s` and determine if it's a palindrome. We maintain a variable to keep track of the longest palindromic substring found so far.
**Time:** O(n^3) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Requires no extra space (O(1) auxiliary space).
**Cons:** Extremely inefficient with a time complexity of O(n^3).; Will likely result in a 'Time Limit Exceeded' error for larger inputs (e.g., n=1000).
### Explanation
This approach is the most straightforward but also the most inefficient. The core idea is to check every single substring of the input string `s` and determine if it's a palindrome. We maintain a variable to keep track of the longest palindromic substring found so far.

### Algorithm
1.  Initialize variables `maxLength` to 1 and `start` to 0 to store the length and starting index of the longest palindrome.
2.  Use nested loops to generate all possible substrings. The outer loop (with index `i`) selects the starting character, and the inner loop (with index `j`) selects the ending character.
3.  For each substring `s[i...j]`, call a helper function `isPalindrome` to check if it's a palindrome.
4.  The `isPalindrome` check is done by comparing characters from both ends of the substring, moving inwards. This takes time proportional to the length of the substring.
5.  If the current substring is a palindrome and its length is greater than `maxLength`, update `maxLength` and `start`.
6.  After checking all substrings, the longest palindromic substring is `s.substring(start, start + maxLength)`.

### Code
```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int n = s.length();
        int start = 0;
        int maxLength = 1;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int len = j - i + 1;
                if (len > maxLength && isPalindrome(s, i, j)) {
                    maxLength = len;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLength);
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize `maxLength = 1` and `start = 0`.
- Iterate through the string with a starting index `i` from 0 to `n-1`.
- For each `i`, iterate with an ending index `j` from `i` to `n-1`.
- Extract the substring `sub` from `i` to `j`.
- Check if `sub` is a palindrome. This check takes O(length of sub) time.
- If `sub` is a palindrome and its length is greater than `maxLength`, update `maxLength` and `start`.
- After all substrings are checked, return the substring starting at `start` with length `maxLength`.

## Dynamic Programming
This approach improves upon the brute-force method by avoiding re-computation. We use a 2D table, `dp[n][n]`, where `dp[i][j]` stores whether the substring `s[i...j]` is a palindrome. The state `dp[i][j]` depends on the state `dp[i+1][j-1]`.
**Time:** O(n^2) · **Space:** O(n^2)
**Pros:** Much more efficient than brute force.; Guaranteed to pass within time limits for typical constraints (n <= 1000).
**Cons:** Requires O(n^2) extra space for the DP table, which can be large for n=1000.
### Explanation
This approach improves upon the brute-force method by avoiding re-computation. We use a 2D table, `dp[n][n]`, where `dp[i][j]` stores whether the substring `s[i...j]` is a palindrome. The state `dp[i][j]` depends on the state `dp[i+1][j-1]`.

### Algorithm
1.  Create a 2D boolean array `dp` of size `n x n`. `dp[i][j]` will be `true` if `s[i...j]` is a palindrome.
2.  Initialize `start` and `maxLength` to track the longest palindrome.
3.  **Base Case 1 (Length 1):** All substrings of length 1 are palindromes. So, set `dp[i][i] = true` for all `i`.
4.  **Base Case 2 (Length 2):** Check all substrings of length 2. If `s.charAt(i) == s.charAt(i+1)`, set `dp[i][i+1] = true` and update `maxLength` and `start`.
5.  **General Case (Length > 2):** Iterate for substring lengths `k` from 3 to `n`. For each length, iterate through all possible start indices `i`. The end index `j` is `i + k - 1`.
6.  A substring `s[i...j]` is a palindrome if the outer characters match (`s.charAt(i) == s.charAt(j)`) AND the inner substring `s[i+1...j-1]` is a palindrome (`dp[i+1][j-1] == true`).
7.  If `dp[i][j]` becomes true, check if its length `k` is the new maximum length and update `start` and `maxLength` accordingly.
8.  Finally, return the substring identified by `start` and `maxLength`.

### Code
```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int maxLength = 1;

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }

        for (int k = 3; k <= n; k++) {
            for (int i = 0; i < n - k + 1; i++) {
                int j = i + k - 1;
                if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    if (k > maxLength) {
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}
```
### Algorithm
- Create a boolean table `dp[n][n]`.
- Initialize `maxLength = 1` and `start = 0`.
- All substrings of length 1 are palindromes, so set `dp[i][i] = true` for all `i`.
- Check for substrings of length 2. If `s[i] == s[i+1]`, then `dp[i][i+1] = true`. Update `maxLength` and `start`.
- Iterate for lengths `k` from 3 to `n`.
- For each length `k`, iterate through all possible starting indices `i`. The ending index `j` will be `i + k - 1`.
- The substring `s[i...j]` is a palindrome if `s[i] == s[j]` and the inner substring `s[i+1...j-1]` is also a palindrome (i.e., `dp[i+1][j-1]` is true).
- If `dp[i][j]` is true, update `maxLength` and `start`.
- After filling the table, return the substring from `start` with `maxLength`.

## Expand Around Center
This approach is an elegant and efficient way to solve the problem in O(n^2) time with O(1) space. Instead of checking every substring, we observe that a palindrome is symmetric around its center. A center can be a single character (for odd-length palindromes) or the space between two characters (for even-length palindromes). There are `2n - 1` such potential centers.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Same time complexity as DP but with O(1) space complexity, making it more memory-efficient.; Often faster in practice than the DP solution due to less overhead and better cache performance.
**Cons:** Still has a quadratic time complexity, which is not optimal.
### Explanation
This approach is an elegant and efficient way to solve the problem in O(n^2) time with O(1) space. Instead of checking every substring, we observe that a palindrome is symmetric around its center. A center can be a single character (for odd-length palindromes) or the space between two characters (for even-length palindromes). There are `2n - 1` such potential centers.

### Algorithm
1.  Initialize `start` and `end` indices to track the boundaries of the longest palindrome found so far.
2.  Iterate through the string with an index `i` from 0 to `n-1`.
3.  For each `i`, treat it as a potential center and expand outwards to find the longest palindrome. We need to check two cases:
    *   **Odd-length palindrome:** The center is the character `s[i]`. We find its length by calling a helper function `expandAroundCenter(s, i, i)`.
    *   **Even-length palindrome:** The center is between `s[i]` and `s[i+1]`. We find its length by calling `expandAroundCenter(s, i, i + 1)`.
4.  The `expandAroundCenter` helper function takes two pointers, `left` and `right`, and expands them (`left--`, `right++`) as long as they are within the string bounds and the characters at these pointers are equal. It returns the length of the palindrome found (`right - left - 1`).
5.  Compare the lengths from the odd and even cases and take the maximum.
6.  If this maximum length is greater than the current longest palindrome's length (`end - start`), update `start` and `end` to reflect the new longest palindrome's boundaries.
7.  After iterating through all possible centers, return `s.substring(start, end + 1)`.

### Code
```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}
```
### Algorithm
- Initialize `start = 0` and `end = 0` to store the boundaries of the longest palindrome found.
- Iterate through the string from `i = 0` to `n-1`.
- For each `i`, consider it as the center of a potential palindrome. There are two cases:
  - **Odd length palindrome**: The center is the character `s[i]`. Expand from this center.
  - **Even length palindrome**: The center is between `s[i]` and `s[i+1]`. Expand from this center.
- Create a helper function `expand(s, left, right)` that expands outwards (`left--`, `right++`) as long as `left >= 0`, `right < n`, and `s.charAt(left) == s.charAt(right)`. It returns the length of the palindrome found.
- For each `i`, call `expand(s, i, i)` and `expand(s, i, i+1)`.
- Let `len` be the maximum of the two lengths returned.
- If `len` is greater than the current longest palindrome's length (`end - start`), update `start` and `end`.
- After the loop, return `s.substring(start, end + 1)`.

## Manacher's Algorithm
Manacher's algorithm is a clever and optimal linear-time solution. It avoids redundant computations by reusing information about previously found palindromes. The core idea is to transform the input string to handle both odd and even length palindromes uniformly and then use an auxiliary array to store the palindrome radius for each center.
**Time:** O(n) · **Space:** O(n)
**Pros:** Optimal time complexity of O(n).; Each character is compared a constant number of times on average.
**Cons:** Significantly more complex to understand and implement correctly compared to other approaches.; The logic, especially the use of the mirror index and right boundary, is not intuitive.
### Explanation
Manacher's algorithm provides a linear-time solution, making it the most efficient approach. It achieves this by cleverly reusing information from previously computed palindromes to avoid redundant character comparisons.

### Algorithm
1.  **Transform String:** First, transform the input string `s` to handle odd and even length palindromes uniformly. Insert a special character (e.g., '#') between each character and at the ends. For example, `s = "babad"` becomes `T = "^#b#a#b#a#d#$"`. The sentinels `^` and `$` prevent out-of-bounds checks during expansion.
2.  **Palindrome Radii Array:** Create an array `P` of the same size as the transformed string `T`. `P[i]` will store the radius of the palindrome centered at `T[i]`.
3.  **Iterate and Expand:** Maintain a `center` (`C`) and a `right` boundary (`R`) of the palindrome found so far that extends furthest to the right. Iterate through `T` with index `i`.
4.  **Key Optimization:** For the current position `i`, find its mirror position `i_mirror = 2*C - i` with respect to the current center `C`. If `i` is within the right boundary `R` (i.e., `R > i`), we can initialize `P[i]` with a guaranteed minimum radius of `min(R - i, P[i_mirror])`. This avoids re-checking characters that are already known to be part of a palindrome.
5.  **Expand:** From this initialized radius, attempt to expand the palindrome centered at `i` by comparing characters `T[i + 1 + P[i]]` and `T[i - 1 - P[i]]`.
6.  **Update Center/Right Boundary:** If the palindrome at `i` expands beyond the current `R`, update `C` to `i` and `R` to `i + P[i]`.
7.  **Find Longest:** After iterating through `T`, find the maximum value `maxLen` in the `P` array and its corresponding center `centerIndex`.
8.  **Convert Back:** Use `maxLen` and `centerIndex` to calculate the start index and length of the longest palindrome in the original string `s` and return the substring.

### Code
```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        StringBuilder tBuilder = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            tBuilder.append('#').append(c);
        }
        tBuilder.append("#$");
        String T = tBuilder.toString();
        int n = T.length();
        int[] P = new int[n];
        int C = 0, R = 0;

        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i;
            if (R > i) {
                P[i] = Math.min(R - i, P[i_mirror]);
            } else {
                P[i] = 0;
            }

            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }
        
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}
```
### Algorithm
- **Transform the string**: Insert a special character (e.g., '#') between each character of `s` and at the ends. For `s = "aba"`, it becomes `T = "#a#b#a#"`. This ensures all palindromes have an odd length.
- Create an array `P` of the same length as the transformed string `T`. `P[i]` will store the radius of the palindrome centered at `T[i]`.
- Initialize `center = 0` and `right = 0`. `center` is the center of the palindrome that extends furthest to the right, and `right` is its right boundary.
- Iterate through the transformed string `T` from `i = 1` to `len(T)-1`.
- For each `i`, find its mirror index `i_mirror = 2 * center - i`.
- **Optimization**: If `i` is within the current right boundary (`right > i`), we can initialize `P[i]` to `min(right - i, P[i_mirror])`.
- **Expand**: Attempt to expand the palindrome centered at `i` by incrementing `P[i]` as long as the characters at `T[i + 1 + P[i]]` and `T[i - 1 - P[i]]` match.
- **Update center and right boundary**: If the palindrome centered at `i` expands beyond the current `right` boundary, update `center` to `i` and `right` to `i + P[i]`.
- Find the maximum value in the `P` array, `maxLen`, and its center, `maxCenter`.
- Convert the result back to the original string's coordinates and return the substring.

# Solutions
### CSharp

```csharp
public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        bool[, ] f = new bool[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; ++j) {
                f[i, j] = true;
            }
        }
        int k = 0, mx = 1;
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i, j] = false;
                if (s[i] == s[j]) {
                    f[i, j] = f[i + 1, j - 1];
                    if (f[i, j] && mx < j - i + 1) {
                        mx = j - i + 1;
                        k = i;
                    }
                }
            }
        }
        return s.Substring(k, mx);
    }
}
```

### Java

```java
class Solution {
public
  String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] f = new boolean[n][n];
    for (var g : f) {
      Arrays.fill(g, true);
    }
    int k = 0, mx = 1;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = false;
        if (s.charAt(i) == s.charAt(j)) {
          f[i][j] = f[i + 1][j - 1];
          if (f[i][j] && mx < j - i + 1) {
            mx = j - i + 1;
            k = i;
          }
        }
      }
    }
    return s.substring(k, k + mx);
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var longestPalindrome = function (
  s,
) {
  const n = s.length;
  const f = Array(n)
    .fill(0)
    .map(() => Array(n).fill(true));
  let k = 0;
  let mx = 1;
  for (let i = n - 2; i >= 0; --i) {
    for (let j = i + 1; j < n; ++j) {
      f[i][j] = false;
      if (s[i] === s[j]) {
        f[i][j] = f[i + 1][j - 1];
        if (f[i][j] && mx < j - i + 1) {
          mx = j - i + 1;
          k = i;
        }
      }
    }
  }
  return s.slice(k, k + mx);
};

```

### CPP

```cpp
class Solution {
public:
  string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> f(n, vector<bool>(n, true));
    int k = 0, mx = 1;
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = false;
        if (s[i] == s[j]) {
          f[i][j] = f[i + 1][j - 1];
          if (f[i][j] && mx < j - i + 1) {
            mx = j - i + 1;
            k = i;
          }
        }
      }
    }
    return s.substr(k, mx);
  }
};

```

### Python

```python
class Solution:
    # class Solution : def longestPalindrome ( self , s : str ) -> str : n = len ( s ) f = [[ True ] * n for _ in range ( n )] k , mx = 0 , 1 for i in range ( n - 2 , - 1 , - 1 ): for j in range ( i + 1 , n ): f [ i ][ j ] = False if s [ i ] == s [ j ]: f [ i ][ j ] = f [ i + 1 ][ j - 1 ] if f [ i ][ j ] and mx < j - i + 1 : k , mx = i , j - i + 1 return s [ k : k + mx ]
    def longestPalindrome(self, s: str) -> str: mlen = 0 start = end = 0 n = len(s) dp = [[False] * n for i in range(n)] for j in range(n): for i in range(j + 1): dp[i][j] = (i == j) or (s[i] == s[j] and j - i == 1) or (s[i] == s[j] and dp[i + 1][j - 1]) if dp[i][j] is True and j - i + 1 > mlen: mlen = j - i + 1 start = i end = j return s[start: end + 1]

```