Scale Engineer

Maximum Number of Non-overlapping Palindrome Substrings

Hard
#2256Time: 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.3 companies
Patterns
Two PointersDynamic ProgrammingGreedy
Data structures
String
Companies
LinkedInSoFiWalmart Labs

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem