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.
This approach uses recursive backtracking to explore all possible solutions incrementally. At each step, it makes a choice and recursively explores further solutions. If a solution is invalid or not optimal, it backtracks and tries the next option.
The C solution demonstrates a recursive function solve, which repeatedly calls itself reducing the 'step' parameter until it hits the base case. This example outlines the concept of recursive backtracking.
Time Complexity: O(2^n), as this approach explores all combinations.
Space Complexity: O(n), due to recursive stack space used during backtracking.
This approach uses dynamic programming to store intermediate results of computations, avoiding recalculating them and thus optimizing the time complexity. It typically involves building a table of results initially filled by base cases and then filled iteratively or recursively with subproblem results.
This C solution implements a memoization technique where results for each step are stored in a dp array. This prevents repeated computations.
Time Complexity: O(n), with each state being computed once.
Space Complexity: O(n), for dp array storage.
We design a function dfs(i, cur, t) that represents the maximum number of partitions we can obtain when currently processing index i of string s, the current prefix already contains the character set cur, and we can still modify t characters. Then the answer is dfs(0, 0, 1).
The execution logic of function dfs(i, cur, t) is as follows:
i geq n, it means we have finished processing string s, return 1.v = 1 \ll (s[i] - 'a') corresponding to the current character s[i], and calculate the updated character set nxt = cur \mid v.nxt exceeds k, it means the current prefix already contains more than k distinct characters. We need to make a partition, increment the partition count by 1, and recursively call dfs(i + 1, v, t). Otherwise, continue recursively calling dfs(i + 1, nxt, t).t > 0, it means we can still modify a character once. We try to change the current character s[i] to any lowercase letter (26 choices in total). For each choice, calculate the updated character set nxt = cur \mid (1 \ll j), and based on whether it exceeds k distinct characters, choose the corresponding recursive call method to update the maximum partition count.The time complexity is O(n times |\Sigma| times k) and the space complexity is O(n times |\Sigma| times k), where n is the length of string s, and |\Sigma| is the size of the character set.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2^n), as this approach explores all combinations. |
| Dynamic Programming | Time Complexity: O(n), with each state being computed once. |
| Memoized Search | — |
| 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 |
Maximize the Number of Partitions After Operations | Intuition From Scratch | Leetcode 3003 | MIK • codestorywithMIK • 10,831 views views
Watch 9 more video solutions →Practice Maximize the Number of Partitions After Operations with our built-in code editor and test cases.
Practice on FleetCode