Skip to main content
Talentd

Maximize the Number of Partitions After Operations - Solution & Explanation

HardStringDynamic ProgrammingBit ManipulationBitmask19 min readAsked at: Hilabs
Practice this problem

Problem Statement

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 s containing at most k distinct characters.
  • Delete the prefix from 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:

  1. The longest prefix containing at most 2 distinct characters is "ac", we remove it and s becomes "bca".
  2. Now The longest prefix containing at most 2 distinct characters is "bc", so we remove it and s becomes "a".
  3. Finally, we remove "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 <= 104
  • s consists only of lowercase English letters.
  • 1 <= k <= 26

Approach Overview

Problem 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 1: Recursive Backtracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), as this approach explores all combinations.
Space Complexity: O(n), due to recursive stack space used during backtracking.

Try this approach in the editor →

Approach 2: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), with each state being computed once.
Space Complexity: O(n), for dp array storage.

Try this approach in the editor →

Approach 3: Memoized Search

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:

  1. If i geq n, it means we have finished processing string s, return 1.
  2. Calculate the bitmask v = 1 \ll (s[i] - 'a') corresponding to the current character s[i], and calculate the updated character set nxt = cur \mid v.
  3. If the number of bits in 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).
  4. If 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.
  5. Use a hash table to cache already computed states to avoid redundant calculations.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.

Dynamic Programming

Time Complexity: O(n), with each state being computed once.
Space Complexity: O(n), for dp array storage.

Memoized Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive BacktrackingExponential (≈ O(n * 26 * branching))O(n)Useful for reasoning about all possible modifications and partitions; not practical for large inputs
Dynamic Programming + BitmaskO(n * 26 * states)O(n * states)Best general solution; efficiently tracks distinct characters and modification state

Video Solution

Maximize the Number of Partitions After Operations | Intuition From Scratch | Leetcode 3003 | MIK • codestorywithMIK • 11,174 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize the Number of Partitions After Operations easy or hard?
Maximize the Number of Partitions After Operations is classified as a Hard problem. The difficulty comes from combining string partitioning logic with a single modification constraint and representing character sets efficiently using bitmasks and dynamic programming.
Maximize the Number of Partitions After Operations Python/Java solution
Python, Java, C++, and other languages typically implement this solution using a recursive DP function with memoization. The function tracks the index in the string, the current bitmask of characters, and whether a modification has been used. Bit operations ensure constant-time updates when adding characters or testing distinct counts.
How to solve Maximize the Number of Partitions After Operations in O(n)?
A near-linear approach processes the string while tracking characters using a bitmask and limiting partitions to k distinct letters. Dynamic Programming stores states for index, mask, and whether a modification was used. Bit operations make updates constant time, and memoization ensures each state is computed once, keeping the overall complexity close to linear with a small constant factor.
What is the best approach for Maximize the Number of Partitions After Operations?
The most effective approach uses Dynamic Programming combined with a bitmask to track distinct characters in the current partition. Each DP state represents the index, current character mask, and whether the single allowed modification has been used. This avoids recomputation and efficiently handles distinct character constraints. The approach runs in roughly O(n * 26 * states) time.
Is Maximize the Number of Partitions After Operations asked at Google/Amazon/Meta?
Problems involving string partitioning with constraints and bitmask-based state tracking frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine dynamic programming with bit manipulation are common in senior-level coding interviews.
What data structure is used in Maximize the Number of Partitions After Operations?
The core technique uses a bitmask to represent the set of characters currently in a partition. Dynamic Programming with memoization stores results for states defined by index, mask, and modification usage. Bit operations such as setting bits and counting set bits help enforce the k distinct character constraint efficiently.
What is the time complexity of Maximize the Number of Partitions After Operations?
The optimized Dynamic Programming solution runs in approximately O(n * 26 * states) time because each character may try up to 26 replacement possibilities when the modification is unused. Space complexity is O(n * states) for memoization. A naive recursive approach without memoization can grow exponentially and is not practical for large inputs.

Ready to solve this problem?

Practice Maximize the Number of Partitions After Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Can Make Palindrome from Substring