3003. Maximize the Number of Partitions After Operations
Approach
Bitmask DP tracking (position, active-char-mask, canChange) to maximize partitions.
Key Techniques
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
// Approach: Bitmask DP tracking (position, active-char-mask, canChange) to maximize partitions.
// Time: O(n * 2^26) Space: O(n * 2^26)
public class Solution
{
// Memoization dictionary: key is Tuple<int, int, int> representing (position, bitmask, canChange)
private Dictionary<(int, int, int), int> memo = new Dictionary<(int, int, int), int>();
private string inputString;
private int maxDistinctChars;
public int MaxPartitionsAfterOperations(string s, int k)
{
this.inputString = s;
this.maxDistinctChars = k;
// Start DFS from position 0, empty bitmask, with 1 change allowed
return Dfs(0, 0, 1);
}
/// <summary>
/// Dynamic programming with memoization to find maximum partitions
/// </summary>
/// <param name="index">current position in string</param>
/// <param name="currentMask">bitmask representing distinct characters in current partition</param>
/// <param name="canChange">flag indicating if we can still change a character (1 = yes, 0 = no)</param>
/// <returns>maximum number of partitions from current state</returns>
private int Dfs(int index, int currentMask, int canChange)
{
// Base case: reached end of string
if (index >= inputString.Length)
return 1;
var memoKey = (index, currentMask, canChange);
if (memo.TryGetValue(memoKey, out int cachedResult))
return cachedResult;
int charBit = 1 << (inputString[index] - 'a');
int newMask = currentMask | charBit;
int maxPartitions;
if (CountBits(newMask) > maxDistinctChars)
// Adding current char exceeds k distinct chars, start new partition
maxPartitions = Dfs(index + 1, charBit, canChange) + 1;
else
// Continue with current partition
maxPartitions = Dfs(index + 1, newMask, canChange);
// Try changing current character (if we haven't used our change yet)
if (canChange > 0)
{
for (int charIndex = 0; charIndex < 26; ++charIndex)
{
newMask = currentMask | (1 << charIndex);
if (CountBits(newMask) > maxDistinctChars)
maxPartitions = Math.Max(maxPartitions, Dfs(index + 1, 1 << charIndex, 0) + 1);
else
maxPartitions = Math.Max(maxPartitions, Dfs(index + 1, newMask, 0));
}
}
memo[memoKey] = maxPartitions;
return maxPartitions;
}
// Helper method to count set bits in an integer
private int CountBits(int n)
{
int count = 0;
while (n != 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
}