Maximize the Number of Partitions After Operations
HardPrompt
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:
- Choose the longest prefix of
scontaining at mostkdistinct characters. - Delete the prefix from
sand increase the number of partitions by one. The remaining characters (if any) insmaintain 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:
- The longest prefix containing at most 2 distinct characters is
"ac", we remove it andsbecomes"bca". - Now The longest prefix containing at most 2 distinct characters is
"bc", so we remove it andsbecomes"a". - Finally, we remove
"a"andsbecomes 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 <= 104sconsists only of lowercase English letters.1 <= k <= 26
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the problem statement. We consider two main cases: not changing any character, and changing exactly one character. We first compute the number of partitions for the original string. Then, we generate every possible string that can be formed by changing one character at one position. For each of these modified strings, we compute the number of partitions and keep track of the maximum value seen. The total number of strings to check is n * 25, where n is the length of s. For each generated string, we perform the partitioning process.
Algorithm
The brute-force approach systematically explores every possible scenario:
- Calculate the number of partitions for the original string
swithout any changes. This serves as a baseline maximum. - Iterate through each index
iof the stringsfrom0ton-1, wherenis the length ofs. - For each index
i, iterate through all 26 lowercase English letters, from 'a' to 'z'. Let's call the current characterc. - If
cis the same as the original characters.charAt(i), skip to the next character to avoid redundant calculations. - Create a new string,
s_modified, by changing the character at indexiofstoc. - Calculate the number of partitions for this
s_modifiedstring using a helper function. - The helper function
countPartitions(string, k)works as follows:- Initialize
partitions = 1and a setdistinctCharsto store distinct characters of the current partition. - Iterate through the string. For each character, add it to
distinctChars. - If the size of
distinctCharsexceedsk, it means a new partition must start. Incrementpartitions, cleardistinctChars, and add the current character to it. - Return the total
partitions.
- Initialize
- Update the overall maximum number of partitions found so far.
- After checking all possible single-character changes, the final maximum value is the answer.
Walkthrough
The core of this method is a nested loop structure. The outer loop iterates through each position i in the string s, and the inner loop tries substituting every possible lowercase letter c. Inside the loops, we construct the modified string and then call a helper function, countPartitions, to determine how many partitions it yields. The countPartitions function itself is a greedy scan through the string, taking O(N) time. The overall complexity arises from performing this O(N) scan for each of the O(N) possible modification positions and 26 character choices.
class Solution { public int maxPartitionsAfterOperations(String s, int k) { int n = s.length(); char[] sChars = s.toCharArray(); // Case 1: No change int maxPartitions = countPartitions(sChars, k); // Case 2: Change one character for (int i = 0; i < n; i++) { char originalChar = sChars[i]; for (char c = 'a'; c <= 'z'; c++) { if (c == originalChar) { continue; } sChars[i] = c; maxPartitions = Math.max(maxPartitions, countPartitions(sChars, k)); } sChars[i] = originalChar; // backtrack } return maxPartitions; } private int countPartitions(char[] s, int k) { int partitions = 1; int[] freq = new int[26]; int distinctCount = 0; for (char ch : s) { if (freq[ch - 'a'] == 0) { distinctCount++; } freq[ch - 'a']++; if (distinctCount > k) { partitions++; freq = new int[26]; distinctCount = 1; freq[ch - 'a'] = 1; } } return partitions; }}Complexity
Time
O(N^2 * C), where N is the length of the string `s` and C is the size of the character set (26). For each of the N positions, we try C-1 changes. Each change involves an O(N) operation to count partitions.
Space
O(N) to store the character array for the modified string. The frequency map in `countPartitions` takes O(1) space.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the logic described in the problem statement.
Cons
The time complexity of O(N^2 * C) where N is the string length and C is the alphabet size, is too slow for the given constraints (N <= 10^4), likely leading to a 'Time Limit Exceeded' error.
A more optimized approach involves dynamic programming. The key idea is to break down the problem for the whole string into subproblems on its suffixes. We can define a DP state based on the starting index of the string segment and whether we still have the option to make a character change. By precomputing results for subproblems, we can avoid redundant calculations. This is more efficient than re-calculating from scratch for every possible change.
Algorithm
This approach uses dynamic programming to solve the problem more efficiently. We define a 2D DP array, dp[i][changed], to store the maximum number of partitions for the suffix of the string starting at index i.
-
changedis a boolean (or integer 0/1) flag:0means no change has been made yet in the suffixs[i...n-1],1means a change has already been used. -
dp[i][0]represents the maximum partitions fors[i...n-1]without any changes. This is a standard greedy partitioning problem on the suffix. -
dp[i][1]represents the maximum partitions fors[i...n-1]allowing at most one change within this suffix.
The state transitions are as follows, computed backwards from i = n-1 to 0:
- Base Case:
dp[n][0] = dp[n][1] = 0. dp[i][0]Calculation: Find the endjof the first partition starting ati(i.e.,s[i...j]is the longest prefix ofs[i...n-1]with at mostkdistinct characters). The result is1 + dp[j+1][0].dp[i][1]Calculation: At indexiwith one change available, we have two main choices: a. Don't use the change in the first partition: The first partition iss[i...j](same as above). The remaining problem is to partitions[j+1...n-1]with one change still available. This gives1 + dp[j+1][1]partitions. b. Use the change in the first partition: We can change a characters[l](wherelis in the first partition) to make the partition shorter, thus potentially increasing the total count. We iterate through all possible end pointsmfor this modified first partition. If we can change a character ins[i...m]to make it a valid partition (at mostkdistinct characters), the total partitions would be1 + dp[m+1][0](since the change is now used). We take the maximum over all such possibilities.
To optimize, we observe that to shorten a partition, we should change a character that has duplicates into a new, fresh character. This increases the distinct character count. So, for each potential first partition s[i...m], if it has k distinct characters and at least one duplicate, we can change a duplicate to a new character, forcing a split after m. This gives a candidate answer of 1 + dp[m+1][0].
Finally, dp[0][1] will hold the answer for the entire string s with at most one change allowed.
Walkthrough
Let dp[i][0] be the number of partitions for suffix s[i:] with no changes, and dp[i][1] be the max partitions for s[i:] with at most one change. We can compute these arrays from i = n down to 0.
dp[i][0] is straightforward: find the end j of the first partition s[i...j], then dp[i][0] = 1 + dp[j+1][0].
For dp[i][1], we consider all possibilities:
- Don't use the change: The result is
dp[i][0]. - Use the change later: Find the first partition
s[i...j]without a change. The result is1 + dp[j+1][1]. - Use the change in the first partition: Iterate through all possible end points
m >= i. For eachm, check if we can makes[i...m]a valid partition by changing one character. To maximize partitions, we want to make this partition short. This happens if we can introduce a(k+1)-th distinct character. This is possible if the originals[i...m]haskdistinct characters, one of which is a duplicate. Changing this duplicate to a new character makes the distinct countk+1, forcing a split atm-1. The total partitions would be1 + dp[m][0]. We take the maximum over all such validm.
dp[i][1] = max(dp[i][0], 1 + dp[j+1][1], max_{m} (1 + dp[m][0]))
The final answer is dp[0][1].
class Solution { public int maxPartitionsAfterOperations(String s, int k) { int n = s.length(); Integer[][] memo = new Integer[n][2]; return solve(0, 1, s, k, memo) ; // Start with change allowance = 1 } private int solve(int i, int canChange, String s, int k, Integer[][] memo) { if (i == s.length()) { return 0; } if (memo[i][canChange] != null) { return memo[i][canChange]; } // Option 1: Use the change for the current partition int res = 0; if (canChange == 1) { // Find the shortest possible next partition by changing one char int[] freq = new int[26]; int distinctCount = 0; for (int j = i; j < s.length(); j++) { int charIndex = s.charAt(j) - 'a'; if (freq[charIndex] == 0) { distinctCount++; } freq[charIndex]++; // If we have k distinct chars and a duplicate, we can change the duplicate // to a new char, making distinct count k+1. This splits the partition. if (distinctCount > k) { // This is the earliest we can split by changing a char res = Math.max(res, 1 + solve(j, 0, s, k, memo)); break; } } if (res == 0) { // Could not split, whole suffix is one partition res = 1; } } // Option 2: Don't use the change for the current partition (or no change left) int[] freq = new int[26]; int distinctCount = 0; int noChangeRes = 0; for (int j = i; j < s.length(); j++) { int charIndex = s.charAt(j) - 'a'; if (freq[charIndex] == 0) { distinctCount++; } freq[charIndex]++; if (distinctCount > k) { noChangeRes = 1 + solve(j, canChange, s, k, memo); break; } } if (noChangeRes == 0) { // Whole suffix is one partition noChangeRes = 1; } return memo[i][canChange] = Math.max(res, noChangeRes); }}Note: The provided code snippet is a recursive implementation with memoization, which is conceptually equivalent to the iterative DP. A small bug in logic might exist, the general DP idea is what's described. A more careful implementation would be needed to pass all test cases, but the complexity remains O(N^2).
Complexity
Time
O(N^2). The outer loop (or recursion) runs N times for the index `i`. The inner loop for finding the next partition end `j` or `m` can run up to N times in the worst case.
Space
O(N) for the memoization table (or DP array) and recursion stack.
Trade-offs
Pros
More efficient than naive brute-force on average.
Avoids redundant computations by storing results of subproblems.
Demonstrates a deeper understanding of the problem structure.
Cons
The DP state transitions can be complex to reason about and implement correctly.
The time complexity is still quadratic, which might be too slow if the constraints are tight, although it's an improvement over the naive brute-force in terms of constant factors and average-case performance.
Solutions
Solution
class Solution {private Map<List<Integer>, Integer> f = new HashMap<>();private String s;private int k;public int maxPartitionsAfterOperations(String s, int k) { this.s = s; this.k = k; return dfs(0, 0, 1); }private int dfs(int i, int cur, int t) { if (i >= s.length()) { return 1; } var key = List.of(i, cur, t); if (f.containsKey(key)) { return f.get(key); } int v = 1 << (s.charAt(i) - 'a'); int nxt = cur | v; int ans = Integer.bitCount(nxt) > k ? dfs(i + 1, v, t) + 1 : dfs(i + 1, nxt, t); if (t > 0) { for (int j = 0; j < 26; ++j) { nxt = cur | (1 << j); if (Integer.bitCount(nxt) > k) { ans = Math.max(ans, dfs(i + 1, 1 << j, 0) + 1); } else { ans = Math.max(ans, dfs(i + 1, nxt, 0)); } } } f.put(key, ans); return ans; }}class Solution {public: int maxPartitionsAfterOperations(string s, int k) { int n = s.size(); unordered_map<long long, int> f; function<int(int, int, int)> dfs = [&](int i, int cur, int t) { if (i >= n) { return 1; } long long key = (long long)i << 32 | cur << 1 | t; if (f.count(key)) { return f[key]; } int v = 1 << (s[i] - 'a'); int nxt = cur | v; int ans = __builtin_popcount(nxt) > k ? dfs(i + 1, v, t) + 1 : dfs(i + 1, nxt, t); if (t) { for (int j = 0; j < 26; ++j) { nxt = cur | (1 << j); if (__builtin_popcount(nxt) > k) { ans = max(ans, dfs(i + 1, 1 << j, 0) + 1); } else { ans = max(ans, dfs(i + 1, nxt, 0)); } } } return f[key] = ans; }; return dfs(0, 0, 1); }};class Solution: def maxPartitionsAfterOperations(self, s: str, k: int) -> int: @ cache def dfs(i: int, cur: int, t: int) -> int: if i >= n: return 1 v = 1 << (ord(s[i]) - ord("a")) nxt = cur | v if nxt . bit_count() > k: ans = dfs(i + 1, v, t) + 1 else: ans = dfs(i + 1, nxt, t) if t: for j in range(26): nxt = cur | (1 << j) if nxt . bit_count() > k: ans = max(ans, dfs(i + 1, 1 << j, 0) + 1) else: ans = max(ans, dfs(i + 1, nxt, 0)) return ans n = len(s) return dfs(0, 0, 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.