Watch 6 video solutions for Maximum Number of Non-overlapping Palindrome Substrings, a hard level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by codingMohan has 3,036 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
k.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 <= 2000s consists of lowercase English letters.Problem Overview: Given a string s and an integer k, choose the maximum number of non‑overlapping substrings such that each substring is a palindrome and its length is at least k. The challenge is balancing palindrome detection with optimal placement so that you maximize the count of valid segments.
Approach 1: Brute Force Enumeration (Exponential time, O(n) space)
Try every possible substring starting at each index and check if it forms a palindrome with length ≥ k. If it does, recursively continue from the next index after the substring. Palindrome validation uses two pointers from both ends of the substring. Because every split decision is explored, the recursion branches heavily and leads to exponential time complexity. This approach demonstrates the problem structure but quickly becomes infeasible for large strings.
Approach 2: Preprocessing + Memoization Search (O(n²) time, O(n²) space)
First precompute which substrings are palindromes. Use dynamic programming or center expansion with two pointers to fill a table isPal[i][j] indicating whether s[i..j] is a palindrome. This preprocessing takes O(n²) time. Then run a memoized DFS (or DP) from each index. At position i, you either skip the character (i + 1) or select a palindrome substring s[i..j] where j - i + 1 ≥ k. If selected, add 1 and continue from j + 1. Memoization stores the best result starting from each index, preventing repeated work. The search ensures non‑overlapping segments while exploring all valid palindrome choices. This combines dynamic programming with precomputed palindrome checks to keep the complexity manageable.
Approach 3: Greedy with Palindrome Expansion (O(n²) time, O(n) space)
Expand palindromes around each center to identify valid substrings of length ≥ k. When scanning from left to right, choose the earliest finishing palindrome that satisfies the length constraint, then jump to the next index after it. The greedy insight is that shorter valid palindromes leave more room for future selections. Expansion relies on the string center technique and often checks only lengths k and k+1 to reduce work. While conceptually simple, careful implementation is required to ensure optimal choices.
Recommended for interviews: Preprocessing palindrome substrings followed by memoized search is the most reliable approach. Interviewers expect you to combine palindrome detection with dynamic programming to enforce the non‑overlapping constraint. Brute force shows you understand the search space, but the memoized DP solution demonstrates practical optimization and problem‑solving maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | Exponential | O(n) | Useful only for understanding the recursion and verifying small inputs |
| Palindrome Preprocessing + Memoized Search | O(n²) | O(n²) | General optimal solution for interview and production constraints |
| Greedy with Center Expansion | O(n²) | O(n) | When prioritizing simpler space usage and greedy earliest-finish selection |