# Maximum Number of Non-overlapping Palindrome Substrings
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-non-overlapping-palindrome-substrings
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [SoFi](https://scaleengineer.com/companies/sofi), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## Problem
You are given a string `s` and a **positive** integer `k`.

Select a set of **non-overlapping** substrings from the string `s` that satisfy the following conditions:

* The **length** of each substring is **at least** `k`.
* Each substring is a **palindrome**.

Return _the **maximum** number of substrings in an optimal selection_.

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

**Example 1:**

**Input:** s = "abaccdbbd", k = 3
**Output:** 2
**Explanation:** We can select the substrings underlined in s = "**aba**cc**dbbd**". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.

**Example 2:**

**Input:** s = "adbcda", k = 2
**Output:** 0
**Explanation:** There is no palindrome substring of length at least 2 in the string.

**Constraints:**

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

# Approaches
## Brute-Force Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the maximum number of non-overlapping palindrome substrings of length at least `k` that can be found in the prefix of the string `s` of length `i` (i.e., `s[0...i-1]`).
**Time:** O(n^3) - There are two nested loops for `i` and `j` which run in `O(n^2)`, and inside the inner loop, the `isPalindrome` check takes up to `O(n)` time. · **Space:** O(n) - for the `dp` array.
**Pros:** Conceptually simple and easy to understand.; Uses minimal space, only `O(n)` for the DP array.
**Cons:** The `O(n^3)` time complexity is inefficient and may lead to a 'Time Limit Exceeded' error on platforms with larger test cases.
### Explanation
We build a `dp` array of size `n+1`, where `n` is the length of `s`. The state transition for `dp[i]` considers two possibilities:

1.  **No palindrome ending at `i-1` is chosen**: In this case, the maximum number of palindromes is the same as for the prefix of length `i-1`, so `dp[i] = dp[i-1]`.
2.  **A palindrome `s[j...i-1]` is chosen**: If the substring `s[j...i-1]` (where `i-j >= k`) is a palindrome, we can potentially form a new optimal solution. This solution would consist of this new palindrome plus the maximum number of palindromes found in the prefix `s[0...j-1]`, which is given by `dp[j]`. We take the maximum over all possible start indices `j`.

The final recurrence is `dp[i] = max(dp[i-1], max_{j | s[j...i-1] is a valid palindrome} (1 + dp[j]))`. The brute-force aspect comes from the nested loops and the linear-time palindrome check within them.

```java
class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1]; // Case 1: Don't form a palindrome ending at i-1
            for (int j = 0; j <= i - k; j++) {
                // Check if s[j...i-1] is a palindrome
                if (isPalindrome(s, j, i - 1)) {
                    // Case 2: Form a palindrome s[j...i-1]
                    dp[i] = Math.max(dp[i], (j > 0 ? dp[j] : 0) + 1);
                }
            }
        }
        return dp[n];
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`, where `n` is the length of `s`. Initialize all elements to 0.
- `dp[i]` will store the maximum number of valid palindromes in the prefix `s[0...i-1]`.
- Loop `i` from 1 to `n`:
  - First, assume no palindrome ends at `i-1`. In this case, the result is the same as for the prefix `s[0...i-2]`. So, set `dp[i] = dp[i-1]`.
  - Then, iterate with a second pointer `j` from 0 up to `i - k`.
  - For each `j`, check if the substring `s[j...i-1]` is a palindrome.
  - If it is, it means we can form a solution by taking this palindrome plus the optimal solution for the prefix `s[0...j-1]`, which is `dp[j]`. We update `dp[i]` with the maximum value found: `dp[i] = max(dp[i], 1 + dp[j])`.
  - The palindrome check itself is done by comparing characters from both ends of the substring, taking `O(length)` time.
- After the loops complete, `dp[n]` holds the result for the entire string.

## DP with Pre-computed Palindromes
This approach improves upon the brute-force DP by optimizing the repeated palindrome checks. We pre-compute whether each possible substring is a palindrome and store the results in a 2D table. This allows for `O(1)` palindrome lookups within the main DP loop.
**Time:** O(n^2) - `O(n^2)` for pre-computation and `O(n^2)` for the main DP loop. · **Space:** O(n^2) - for the `isPalindrome` table.
**Pros:** Reduces the time complexity to `O(n^2)`, which is a significant improvement and efficient enough for the given constraints.
**Cons:** Requires `O(n^2)` space for the pre-computation table, which can be large for `n=2000`.
### Explanation
The bottleneck in the previous approach was the `isPalindrome` check inside the loops. We can eliminate this redundant work by pre-calculating all possible palindrome substrings.

We use a 2D DP table, `isPalindrome[i][j]`, which is `true` if `s[i...j]` is a palindrome. This table is filled as follows:
- `isPalindrome[i][i] = true` for all `i`.
- `isPalindrome[i][i+1] = (s.charAt(i) == s.charAt(i+1))`.
- For longer substrings `s[i...j]`, `isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1])`.

After this `O(n^2)` pre-computation, the main DP logic remains the same, but the check is now a constant-time table lookup. This reduces the overall time complexity to `O(n^2)`.

```java
class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];

        // Pre-compute all palindrome substrings
        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) {
                        isPalindrome[i][j] = true;
                    } else {
                        isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                    }
                }
            }
        }

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            for (int j = 0; j <= i - k; j++) {
                if (isPalindrome[j][i - 1]) {
                    dp[i] = Math.max(dp[i], (j > 0 ? dp[j] : 0) + 1);
                }
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- First, create a 2D boolean array `isPalindrome` of size `n x n`.
- Populate this table in `O(n^2)` time. A substring `s[i...j]` is a palindrome if its first and last characters (`s[i]` and `s[j]`) are the same, and the inner substring `s[i+1...j-1]` is also a palindrome. Base cases are substrings of length 1 and 2.
- Once the `isPalindrome` table is ready, use the same DP logic as the brute-force approach.
- Create a DP array `dp` of size `n + 1`.
- Loop `i` from 1 to `n`:
  - Set `dp[i] = dp[i-1]`.
  - Loop `j` from 0 to `i - k`:
    - Instead of a linear-time check, use the pre-computed table: `if (isPalindrome[j][i-1])`.
    - If true, update `dp[i] = max(dp[i], 1 + dp[j])`.
- Return `dp[n]`.

## Optimized DP with Expanding Centers
This is the most efficient approach, optimizing both time and space. It uses dynamic programming but avoids the `O(n^2)` space for a pre-computation table. Instead, it finds palindromes on-the-fly using the 'expand from center' technique and updates the DP table in a single pass.
**Time:** O(n^2) - The outer loop runs `n` times, and the inner 'expand from center' loops visit each character pair at most a constant number of times across all iterations, leading to `O(n^2)` total operations. · **Space:** O(n) - for the `dp` array.
**Pros:** Optimal time complexity of `O(n^2)`.; Optimal space complexity of `O(n)`, avoiding the large 2D table.
**Cons:** The logic can be slightly more complex to reason about compared to the standard DP formulation.
### Explanation
We maintain the same DP state `dp[i]` as in other approaches. However, we change the iteration strategy. Instead of iterating through all substrings for each `dp[i]`, we iterate through all `2n-1` possible palindrome centers. For each center, we expand outwards to find all palindromes centered there.

When we find a valid palindrome `s[l...r]` (length at least `k`), we know it ends at index `r`. This gives us an opportunity to update `dp[r+1]`. The new value would be `1` (for the palindrome `s[l...r]`) plus the optimal solution for the prefix ending just before this palindrome, which is `dp[l]`. Thus, we perform the update: `dp[r+1] = max(dp[r+1], dp[l] + 1)`.

By iterating through centers `i` from `0` to `n-1`, we ensure that when we calculate an update for `dp[r+1]` using `dp[l]`, the value `dp[l]` (where `l <= i < r+1`) has already been finalized. This method cleverly integrates palindrome detection and DP updates, achieving `O(n^2)` time with only `O(n)` space.

```java
class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        int[] dp = new int[n + 1];

        for (int i = 0; i < n; i++) {
            // Propagate the previous result. This is crucial for correctness,
            // as it covers the case where no new palindrome is formed.
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);

            // Case 1: Odd length palindromes centered at i
            int l = i, r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                if (r - l + 1 >= k) {
                    dp[r + 1] = Math.max(dp[r + 1], (l > 0 ? dp[l] : 0) + 1);
                }
                l--;
                r++;
            }

            // Case 2: Even length palindromes centered at i, i+1
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                if (r - l + 1 >= k) {
                    dp[r + 1] = Math.max(dp[r + 1], (l > 0 ? dp[l] : 0) + 1);
                }
                l--;
                r++;
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`, initialized to 0. `dp[i]` stores the max palindromes in `s[0...i-1]`.
- Loop `i` from 0 to `n-1`. This `i` will serve as a potential center for palindromes.
- Inside the loop, first propagate the previous best result: `dp[i+1] = max(dp[i+1], dp[i])`. This handles the gaps between chosen palindromes.
- **Check for odd-length palindromes**: Expand from the center `i`. Initialize `l=i, r=i`.
  - While `l >= 0`, `r < n`, and `s[l] == s[r]`:
    - If the length `r-l+1 >= k`, we have found a valid palindrome `s[l...r]`.
    - This palindrome can extend a solution from the prefix `s[0...l-1]`. Update `dp[r+1] = max(dp[r+1], dp[l] + 1)`.
    - Decrement `l` and increment `r` to expand further.
- **Check for even-length palindromes**: Expand from the center `i, i+1`. Initialize `l=i, r=i+1`.
  - While `l >= 0`, `r < n`, and `s[l] == s[r]`:
    - If length `r-l+1 >= k`, we have a valid palindrome `s[l...r]`.
    - Update `dp[r+1] = max(dp[r+1], dp[l] + 1)`.
    - Decrement `l` and increment `r`.
- After the loop finishes, `dp[n]` contains the final answer.

# Solutions
### Java

```java
class Solution { private boolean [][] dp ; private int [] f ; private String s ; private int n ; private int k ; public int maxPalindromes ( String s , int k ) { n = s . length (); f = new int [ n ]; this . s = s ; this . k = k ; dp = new boolean [ n ][ n ]; for ( int i = 0 ; i < n ; ++ i ) { Arrays . fill ( dp [ i ], true ); f [ i ] = - 1 ; } for ( int i = n - 1 ; i >= 0 ; -- i ) { for ( int j = i + 1 ; j < n ; ++ j ) { dp [ i ][ j ] = s . charAt ( i ) == s . charAt ( j ) && dp [ i + 1 ][ j - 1 ]; } } return dfs ( 0 ); } private int dfs ( int i ) { if ( i >= n ) { return 0 ; } if ( f [ i ] != - 1 ) { return f [ i ]; } int ans = dfs ( i + 1 ); for ( int j = i + k - 1 ; j < n ; ++ j ) { if ( dp [ i ][ j ]) { ans = Math . max ( ans , 1 + dfs ( j + 1 )); } } f [ i ] = ans ; return ans ; } }
```

### CPP

```cpp
class Solution { public: int maxPalindromes ( string s , int k ) { int n = s . size (); vector < vector < bool >> dp ( n , vector < bool > ( n , true )); vector < int > f ( n , - 1 ); for ( int i = n - 1 ; i >= 0 ; -- i ) { for ( int j = i + 1 ; j < n ; ++ j ) { dp [ i ][ j ] = s [ i ] == s [ j ] && dp [ i + 1 ][ j - 1 ]; } } function < int ( int ) > dfs = [ & ]( int i ) -> int { if ( i >= n ) return 0 ; if ( f [ i ] != - 1 ) return f [ i ]; int ans = dfs ( i + 1 ); for ( int j = i + k - 1 ; j < n ; ++ j ) { if ( dp [ i ][ j ]) { ans = max ( ans , 1 + dfs ( j + 1 )); } } f [ i ] = ans ; return ans ; }; return dfs ( 0 ); } };
```

### Python

```python
class Solution : def maxPalindromes ( self , s : str , k : int ) -> int : @ cache def dfs ( i ): if i >= n : return 0 ans = dfs ( i + 1 ) for j in range ( i + k - 1 , n ): if dp [ i ][ j ]: ans = max ( ans , 1 + dfs ( j + 1 )) return ans n = len ( s ) dp = [[ True ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i + 1 , n ): dp [ i ][ j ] = s [ i ] == s [ j ] and dp [ i + 1 ][ j - 1 ] ans = dfs ( 0 ) dfs . cache_clear () return ans
```