Watch 10 video solutions for Maximize the Number of Partitions After Operations, a hard level problem involving String, Dynamic Programming, Bit Manipulation. This walkthrough by codestorywithMIK has 10,831 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s and an integer k.
First, you are allowed to change at most one index in s to another lowercase English letter.
After that, do the following partitioning operation until s is empty:
s containing at most k distinct characters.s and increase the number of partitions by one. The remaining characters (if any) in s maintain their initial order.Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one index to change.
Example 1:
Input: s = "accca", k = 2
Output: 3
Explanation:
The optimal way is to change s[2] to something other than a and c, for example, b. then it becomes "acbca".
Then we perform the operations:
"ac", we remove it and s becomes "bca"."bc", so we remove it and s becomes "a"."a" and s becomes empty, so the procedure ends.Doing the operations, the string is divided into 3 partitions, so the answer is 3.
Example 2:
Input: s = "aabaab", k = 3
Output: 1
Explanation:
Initially s contains 2 distinct characters, so whichever character we change, it will contain at most 3 distinct characters, so the longest prefix with at most 3 distinct characters would always be all of it, therefore the answer is 1.
Example 3:
Input: s = "xxyz", k = 1
Output: 4
Explanation:
The optimal way is to change s[0] or s[1] to something other than characters in s, for example, to change s[0] to w.
Then s becomes "wxyz", which consists of 4 distinct characters, so as k is 1, it will divide into 4 partitions.
Constraints:
1 <= s.length <= 104s consists only of lowercase English letters.1 <= k <= 26Problem Overview: You are given a string s and an integer k. The goal is to split the string into the maximum number of partitions such that each partition contains at most k distinct characters. Before partitioning, you are allowed to modify at most one character in the string. The challenge is deciding where to split and whether changing a character increases the number of valid partitions.
Approach 1: Recursive Backtracking (Exponential Time)
This approach explores all possible partition boundaries while optionally changing one character to any of the 26 lowercase letters. Maintain a running set or bitmask of characters in the current segment and start a new partition whenever the number of distinct characters exceeds k. During recursion, try both cases: keep the character as is or replace it (if the modification hasn't been used yet). This brute-force exploration guarantees the correct answer but quickly becomes expensive because every index can branch into up to 26 possibilities. Time complexity is roughly O(n * 26 * branching) in the worst case with O(n) recursion stack space. Useful mainly for understanding the decision space before optimizing.
Approach 2: Dynamic Programming + Bitmask (Optimal)
The optimized approach uses dynamic programming combined with a bitmask to track distinct characters in the current partition. Represent the character set using a 26-bit mask where each bit indicates whether a letter is present. The DP state is typically defined as dp(i, mask, changed): the maximum partitions starting at index i, given the current character mask and whether the one allowed modification has been used. When adding s[i] causes the number of set bits to exceed k, a new partition is started and the mask resets.
If the modification has not been used, try replacing s[i] with any other character and evaluate how that affects the mask and partition count. Memoization avoids recomputing states, and bit operations make distinct-character checks fast. The state transitions rely heavily on bitmask techniques like setting bits and counting them using popcount. This reduces the complexity to roughly O(n * 26 * states) with space O(n * states), which works within constraints.
Recommended for interviews: The Dynamic Programming + Bitmask solution is what interviewers expect. The brute-force recursion shows you understand the search space and the effect of the single allowed modification. The optimized DP demonstrates strong problem-solving skills by compressing character sets into a bitmask and caching overlapping subproblems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | Exponential (≈ O(n * 26 * branching)) | O(n) | Useful for reasoning about all possible modifications and partitions; not practical for large inputs |
| Dynamic Programming + Bitmask | O(n * 26 * states) | O(n * states) | Best general solution; efficiently tracks distinct characters and modification state |