Maximum Number of Non-overlapping Palindrome Substrings

Maximum Number of Non-overlapping Palindrome Substrings

What is this problem about?

The Maximum Number of Non-overlapping Palindrome Substrings coding problem gives you a string s and an integer k. You want to find the maximum number of non-overlapping palindrome substrings of length at least k. Each selected substring must be a palindrome, have length ≥ k, and must not overlap with any other selected substring.

Why is this asked in interviews?

Microsoft, SoFi, Salesforce, LinkedIn, Oracle, and Walmart Labs include this problem because it combines palindrome detection (using DP or Manacher's algorithm) with a greedy interval selection. The greedy insight — always pick the shortest valid palindrome ending as early as possible — is the same as the classic interval scheduling maximization. This problem tests both string algorithms and greedy thinking.

Algorithmic pattern used

DP palindrome check + Greedy selection: First, precompute isPalin[i][j] = whether s[i..j] is a palindrome (O(n²) DP or Manacher's). Then, greedily iterate left to right: for each position i, find the leftmost j ≥ i+k-1 such that s[i..j] is a palindrome. If found, select this substring (count++), move to j+1, and continue. This greedy "start as early, end as early as possible" maximizes the number of non-overlapping palindromes.

Example explanation

s = "aabbaabaab", k = 3.

• At i=0: find shortest palindrome starting at 0 with length ≥ 3. s[0..2]="aab" not palindrome. s[0..3]="aabb" no. s[0..4]="aabba" yes! Select [0,4]. Count=1. Move to i=5.
• At i=5: s[5..7]="baa" no. s[5..8]="baab" yes! Select [5,8]. Count=2. Move to i=9.
• i=9: remaining = "b". Length 1 < k=3. Stop.
• Answer = 2.

Common mistakes candidates make

• Not finding the shortest valid palindrome per position: Selecting a long palindrome when a shorter one exists wastes space, reducing total count.
• O(n³) palindrome check in greedy: Using naive palindrome checking inside the greedy gives O(n³) total. Precompute palindrome table to make each check O(1).
• Not enforcing minimum length k: Palindromes shorter than k are not valid; including them violates the constraint.

Interview preparation tip

For the Two Pointers String Greedy Dynamic Programming interview pattern, the "palindrome DP table + greedy interval selection" combination is reusable. Build the palindrome table once, then apply any interval selection strategy (earliest-end greedy for max count, or DP for weighted selection). Manacher's algorithm is the O(n) alternative to the O(n²) palindrome DP — worth knowing for follow-up questions.