Maximum Number of Non-overlapping Palindrome Substrings

HARD

Description

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 = "abaccdbbd". 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

Checkout 3 different approaches to solve Maximum Number of Non-overlapping Palindrome Substrings. Click on different approaches to view the approach and algorithm in detail.

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]).

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.

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:

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

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n) - for the `dp` array.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Number of Non-overlapping Palindrome Substrings. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Maximum Number of Non-overlapping Palindrome Substrings

Patterns:

Two PointersDynamic ProgrammingGreedy

Data Structures:

String

Companies:

LinkedIn |SoFi |Walmart Labs |