# Palindromic Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/palindromic-substrings)
Canonical: https://scaleengineer.com/dsa/problems/palindromic-substrings
**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), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Cisco](https://scaleengineer.com/companies/cisco), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [LinkedIn](https://scaleengineer.com/companies/linkedin), [PayPal](https://scaleengineer.com/companies/paypal), [SoFi](https://scaleengineer.com/companies/sofi), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [Wayfair](https://scaleengineer.com/companies/wayfair), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Millennium](https://scaleengineer.com/companies/millennium), [Netskope](https://scaleengineer.com/companies/netskope)
---
## Problem
Given a string `s`, return _the number of **palindromic substrings** in it_.

A string is a **palindrome** when it reads the same backward as forward.

A **substring** is a contiguous sequence of characters within the string.

**Example 1:**

**Input:** s = "abc"
**Output:** 3
**Explanation:** Three palindromic strings: "a", "b", "c".

**Example 2:**

**Input:** s = "aaa"
**Output:** 6
**Explanation:** Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force: Generate and Check
The most straightforward approach is to generate every possible substring and then, for each one, check if it is a palindrome. If it is, we increment a counter. This method is easy to conceptualize but is the least efficient.
**Time:** O(n³), where n is the length of the string. There are O(n²) substrings, and checking if a substring is a palindrome takes O(n) time in the worst case. · **Space:** O(1) extra space, as the palindrome check can be done in-place with pointers without allocating significant new memory.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Very inefficient with a cubic time complexity, making it unsuitable for large inputs.; Performs many redundant palindrome checks for overlapping substrings.
### Explanation
This approach iterates through all possible start and end indices to define a substring. For each substring generated, a separate check is performed to determine if it's a palindrome. A simple way to check for a palindrome is to compare the substring with its reverse, or more efficiently, use a two-pointer technique. The outer loops run in O(n²) time to generate all substrings, and the palindrome check for each substring of length `k` takes O(k) time. In the worst case, this leads to an overall time complexity of O(n³).

```java
class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Generate all possible substrings of the input string `s` using two nested loops. The outer loop with index `i` determines the start of the substring, and the inner loop with index `j` determines the end.
*   For each substring, create a helper function `isPalindrome` to check if it's a palindrome.
*   The `isPalindrome` function uses two pointers, `start` and `end`, initialized to the beginning and end of the substring. It checks if characters at these pointers are equal while moving them towards the center.
*   If the helper function returns `true`, increment the `count`.
*   After checking all substrings, return the final `count`.

## Dynamic Programming
A more optimized approach uses dynamic programming to avoid re-computing whether a substring is a palindrome. We use a 2D table to store the results for all substrings. The result for a larger substring can be efficiently calculated using the stored results of smaller substrings.
**Time:** O(n²), as we iterate through the O(n²) states of the DP table, and each state is computed in O(1) time. · **Space:** O(n²), for the 2D DP table used to store palindrome information for all substrings.
**Pros:** Significantly more efficient than the brute-force approach.; Systematic and avoids redundant computations by storing intermediate results.
**Cons:** Requires O(n²) space for the DP table, which can be substantial for large strings.
### Explanation
We define `dp[i][j]` as a boolean that is true if the substring from index `i` to `j` (inclusive) is a palindrome. The key insight is that a string `s[i...j]` is a palindrome if and only if its first and last characters (`s[i]` and `s[j]`) are the same, and the substring between them (`s[i+1...j-1]`) is also a palindrome. We can build up the `dp` table by considering substrings of increasing length. We start with substrings of length 1 (all single characters are palindromes), then length 2, and so on, up to length `n`. Each time we find a palindrome (i.e., set `dp[i][j]` to true), we increment our total count.

```java
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        boolean[][] dp = new boolean[n][n];
        int count = 0;

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len <= 2) { // Length 1 or 2
                        dp[i][j] = true;
                    } else { // Length > 2
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Create a 2D boolean array `dp[n][n]`, where `n` is the string length. `dp[i][j]` will be `true` if the substring `s[i...j]` is a palindrome.
*   Initialize a counter `count` to 0.
*   Iterate through substring lengths `len` from 1 to `n`.
*   For each `len`, iterate through all possible start indices `i`.
*   The end index `j` is calculated as `i + len - 1`.
*   **Base Case (len=1):** `dp[i][i]` is always `true`. Increment `count`.
*   **Base Case (len=2):** `dp[i][i+1]` is `true` if `s.charAt(i) == s.charAt(i+1)`. If true, increment `count`.
*   **Recursive Step (len > 2):** `dp[i][j]` is `true` if `s.charAt(i) == s.charAt(j)` and the inner substring `s[i+1...j-1]` is a palindrome (i.e., `dp[i+1][j-1]` is `true`). If true, increment `count`.
*   Return the total `count`.

## Expand Around Center
This clever approach improves upon the DP solution's space complexity. It's based on the observation that every palindrome has a center. A center can be a single character (for odd-length palindromes like 'racecar') or the space between two characters (for even-length palindromes like 'aabbaa'). We can iterate through all `2n-1` possible centers and expand outwards to count all palindromes.
**Time:** O(n²). There are `2n-1` centers, and expansion from each center can take up to O(n) time in the worst case (e.g., a string of all the same characters). · **Space:** O(1), as we only use a few variables to keep track of pointers and the count, regardless of the input string size.
**Pros:** Optimal space complexity of O(1).; Time complexity is the same as the DP approach, O(n²).; Often simpler to implement than the DP solution.
**Cons:** While space-efficient, the time complexity is still quadratic, which might be too slow for very large inputs under strict time limits.
### Explanation
Instead of building a table, we consider each possible center of a palindrome. For a string of length `n`, there are `n` single-character centers and `n-1` between-character centers. We loop through each of these `2n-1` centers. From each center, we expand outwards with two pointers, `left` and `right`. As long as the pointers are valid and the characters at these pointers match, we have found a palindrome and increment our count. Then, we move the pointers further out (`left--`, `right++`) and check again. This process continues until the characters don't match or we go out of bounds.

```java
class Solution {
    int count = 0;

    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        for (int i = 0; i < s.length(); i++) {
            // Odd length palindromes, centered at i
            expandAroundCenter(s, i, i);
            // Even length palindromes, centered between i and i+1
            expandAroundCenter(s, i, i + 1);
        }

        return count;
    }

    private void expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
    }
}
```
### Algorithm
*   Initialize a global or member variable `count` to 0.
*   Iterate through the string from `i = 0` to `n-1`.
*   For each index `i`, treat it as the center of a potential palindrome and find all palindromes centered at `i`.
*   Call a helper function `expandAroundCenter(s, i, i)` to find all odd-length palindromes centered at `i`.
*   Call the same helper function `expandAroundCenter(s, i, i+1)` to find all even-length palindromes centered between `i` and `i+1`.
*   The `expandAroundCenter` function takes the string and two pointers, `left` and `right`. It expands outwards from this center as long as `left` and `right` are within bounds and `s.charAt(left) == s.charAt(right)`. For each valid expansion, it increments the `count`.
*   Return the total `count`.

## Manacher's Algorithm
Manacher's algorithm is the most optimal solution, achieving a linear time complexity. It is an extension of the 'Expand Around Center' idea but uses properties of palindromes to avoid redundant character comparisons. It does this by maintaining the boundary of the rightmost-extending palindrome found so far and using its internal symmetry to initialize the palindrome radius for new centers.
**Time:** O(n). The algorithm processes the string in a single pass. The expansion loop, while nested, has an amortized complexity of O(n) because the `right` boundary pointer only ever moves forward. · **Space:** O(n), required for the transformed string and the radius array `p`.
**Pros:** Optimal O(n) time complexity.; The fastest known algorithm for this problem.
**Cons:** Significantly more complex to understand and implement correctly than the other approaches.; Requires O(n) extra space, whereas the 'Expand Around Center' approach uses O(1).
### Explanation
The algorithm first transforms the string (e.g., `"aba"` -> `"#a#b#a#"`) so that every palindrome has a distinct center and an odd length. It then iterates through the transformed string, calculating the radius of the palindrome centered at each position. The core optimization comes from using a `p` array, where `p[i]` stores the radius of the palindrome at center `i`. When calculating `p[i]`, if `i` is inside a previously found larger palindrome, we can use the information from its 'mirror' position to get a guaranteed minimum radius for `p[i]`, reducing the number of character comparisons needed for expansion. The total number of character comparisons across the entire algorithm is amortized to O(n). The number of palindromic substrings is then calculated by summing up the contributions from each center, where a palindrome of length `L` in the original string contributes `(L+1)/2` to the total count.

```java
class Solution {
    public int countSubstrings(String s) {
        StringBuilder tBuilder = new StringBuilder("#");
        for (char c : s.toCharArray()) {
            tBuilder.append(c).append('#');
        }
        String t = tBuilder.toString();
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0;
        int count = 0;

        for (int i = 1; i < n - 1; i++) {
            int iMirror = 2 * center - i;
            if (i < right) {
                p[i] = Math.min(right - i, p[iMirror]);
            }

            while (i - 1 - p[i] >= 0 && i + 1 + p[i] < n && t.charAt(i - 1 - p[i]) == t.charAt(i + 1 + p[i])) {
                p[i]++;
            }

            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            
            count += (p[i] + 1) / 2;
        }
        return count;
    }
}
```
### Algorithm
*   **Preprocessing:** Transform the input string `s` into a new string `t` by inserting a special character (e.g., '#') between each character and at the ends. This handles odd and even length palindromes uniformly.
*   **Initialization:** Create a radius array `p` of the same size as `t`. Initialize `center = 0`, `right = 0` (for the rightmost palindrome found), and `count = 0`.
*   **Iteration:** Loop `i` from `1` to `t.length() - 1`.
    *   Calculate the mirror index `i_mirror = 2 * center - i`.
    *   If `i` is within the current rightmost palindrome (`i < right`), initialize `p[i]` using the mirror's radius: `p[i] = min(right - i, p[i_mirror])`. This is the key optimization.
    *   Expand `p[i]` by checking characters: `while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) { p[i]++; }`.
    *   If the palindrome at `i` extends beyond `right`, update `center` and `right`.
*   **Counting:** For each `i`, the radius `p[i]` corresponds to a palindrome of length `p[i]` in the original string. This longest palindrome contains `(p[i] + 1) / 2` smaller palindromes centered at the same spot. Add this value to the total `count`.
*   Return `count`.

# Solutions
### Java

```java
class Solution { public int countSubstrings ( String s ) { StringBuilder sb = new StringBuilder ( "^#" ); for ( char ch : s . toCharArray ()) { sb . append ( ch ). append ( '#' ); } String t = sb . append ( '$' ). toString (); int n = t . length (); int [] p = new int [ n ]; int pos = 0 , maxRight = 0 ; int ans = 0 ; for ( int i = 1 ; i < n - 1 ; i ++) { p [ i ] = maxRight > i ? Math . min ( maxRight - i , p [ 2 * pos - i ]) : 1 ; while ( t . charAt ( i - p [ i ]) == t . charAt ( i + p [ i ])) { p [ i ]++; } if ( i + p [ i ] > maxRight ) { maxRight = i + p [ i ]; pos = i ; } ans += p [ i ] / 2 ; } return ans ; } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var countSubstrings = function (
  s,
) {
  let ans = 0;
  const n = s.length;
  for (let k = 0; k < n * 2 - 1; ++k) {
    let i = k >> 1;
    let j = (k + 1) >> 1;
    while (~i && j < n && s[i] == s[j]) {
      ++ans;
      --i;
      ++j;
    }
  }
  return ans;
};

```

### CPP

```cpp
class Solution { public: int countSubstrings ( string s ) { int ans = 0 ; int n = s . size (); for ( int k = 0 ; k < n * 2 - 1 ; ++ k ) { int i = k / 2 , j = ( k + 1 ) / 2 ; while ( ~ i && j < n && s [ i ] == s [ j ]) { ++ ans ; -- i ; ++ j ; } } return ans ; } };
```

### Python

```python
class Solution:
    def countSubstrings(self, s: str) -> int: t = '^#' + '#' . join(s) + '#$' n = len(t) p = [0 for _ in range(n)] pos, maxRight = 0, 0 ans = 0 for i in range(1, n - 1): p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1 while t[i - p[i]] == t[i + p[i]]: p[i] += 1 if i + p[i] > maxRight: maxRight = i + p[i] pos = i ans += p[i] // 2 return ans

```