Skip to main content
Talentd

Maximum Number of Non-overlapping Palindrome Substrings - Solution & Explanation

HardTwo PointersStringDynamic ProgrammingGreedy7 min readAsked at: Microsoft, Oracle, Salesforce +2
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

First, preprocess the string s to get dp[i][j], which represents whether the substring s[i,..j] is a palindrome.

Then, define a function dfs(i) to represent the maximum number of non-overlapping palindrome substrings that can be selected from the substring s[i,..], i.e.,

$ \begin{aligned} dfs(i) &= \begin{cases} 0, & i geq n \ max{dfs(i + 1), max_{j geq i + k - 1} {dfs(j + 1) + 1}}, & i < n \end{cases} \end{aligned}

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s$.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationExponentialO(n)Useful only for understanding the recursion and verifying small inputs
Palindrome Preprocessing + Memoized SearchO(n²)O(n²)General optimal solution for interview and production constraints
Greedy with Center ExpansionO(n²)O(n)When prioritizing simpler space usage and greedy earliest-finish selection

Video Solution

Dynamic Programming | Weekly Contest 319 | Maximum Number of Non-overlapping Palindrome Substrings • codingMohan • 3,110 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Maximum Number of Non-overlapping Palindrome Substrings easy or hard?
LeetCode classifies this problem as Hard because it combines multiple concepts: palindrome detection, dynamic programming, and greedy decision making. Efficient solutions require preprocessing and careful state transitions to avoid exponential exploration.
Maximum Number of Non-overlapping Palindrome Substrings Python/Java solution
Implement the solution by first building a palindrome lookup table using DP or center expansion. Then run a memoized DFS or bottom-up DP to compute the maximum number of valid non-overlapping substrings. The approach translates cleanly to Python, Java, C++, and Go using arrays for the palindrome table and memoization.
How to solve Maximum Number of Non-overlapping Palindrome Substrings in O(n²)?
Precompute a 2D table where isPal[i][j] indicates if substring s[i..j] is a palindrome. Then use dynamic programming where dp[i] stores the maximum palindromes obtainable starting from index i. For each index, either skip the character or choose a palindrome of length ≥ k and jump to j+1. Memoization ensures each state is computed once, giving O(n²) total time.
What is the best approach for Maximum Number of Non-overlapping Palindrome Substrings?
The most reliable approach is palindrome preprocessing combined with memoized dynamic programming. First compute whether each substring s[i..j] is a palindrome in O(n²). Then run a DP or DFS with memoization that decides whether to skip a character or take a palindrome substring of length ≥ k. This ensures non-overlapping selection while maximizing the count.
Is Maximum Number of Non-overlapping Palindrome Substrings asked at Google/Amazon/Meta?
Palindrome partitioning and dynamic programming string problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving palindrome detection, segmentation, or maximizing valid substrings are common because they test DP design and string manipulation skills.
What data structure is used in Maximum Number of Non-overlapping Palindrome Substrings?
The solution primarily uses a dynamic programming table to store palindrome information and a memoization array or map for DP states. Two pointers or center expansion are often used during preprocessing to detect palindromes efficiently.
What is the time complexity of Maximum Number of Non-overlapping Palindrome Substrings?
The optimal solution runs in O(n²) time. O(n²) is used to precompute palindrome substrings using dynamic programming or center expansion, and the memoized DP search processes each index once with bounded checks. Space complexity is typically O(n²) for the palindrome table plus O(n) for memoization.

Ready to solve this problem?

Practice Maximum Number of Non-overlapping Palindrome Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Maximum Number of Non-Overlapping Substrings