3003. Maximize the Number of Partitions After Operations LeetCode Solution
In this guide, you will get 3003. Maximize the Number of Partitions After Operations LeetCode Solution with the best time and space complexity. The solution to Maximize the Number of Partitions After Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize the Number of Partitions After Operations
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:
The longest prefix containing at most 2 distinct characters is “ac”, we remove it and s becomes “bca”.
Now The longest prefix containing at most 2 distinct characters is “bc”, so we remove it and s becomes “a”.
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
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(26n) = O(n)
3003. Maximize the Number of Partitions After Operations LeetCode Solution in C++
class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
unordered_map<long, int> mem;
return maxPartitionsAfterOperations(s, 0, true, 0, k, mem) + 1;
}
private:
// Returns the maximum number of partitions of s[i..n), where `canChange` is
// true if we can still change a letter, and `mask` is the bitmask of the
// letters we've seen.
int maxPartitionsAfterOperations(const string& s, int i, bool canChange,
int mask, int k,
unordered_map<long, int>& mem) {
if (i == s.length())
return 0;
long key = static_cast<long>(i) << 27 | (canChange ? 1 : 0) << 26 | mask;
if (const auto it = mem.find(key); it != mem.end())
return it->second;
// Initialize the result based on the current letter.
int res = getRes(s, i, canChange, mask, 1 << (s[i] - 'a'), k, mem);
// If allowed, explore the option to change the current letter.
if (canChange)
for (int j = 0; j < 26; ++j)
res = max(res, getRes(s, i, false, mask, 1 << j, k, mem));
return mem[key] = res;
}
int getRes(const string& s, int i, bool nextCanChange, unsigned mask,
int newBit, int k, unordered_map<long, int>& mem) {
const unsigned nextMask = mask | newBit;
if (popcount(nextMask) > k) // fresh start
return 1 + maxPartitionsAfterOperations(s, i + 1, nextCanChange, newBit,
k, mem);
return maxPartitionsAfterOperations(s, i + 1, nextCanChange, nextMask, k,
mem);
}
}; /* code provided by PROGIEZ */
3003. Maximize the Number of Partitions After Operations LeetCode Solution in Java
class Solution {
public int maxPartitionsAfterOperations(String s, int k) {
Map<Long, Integer> mem = new HashMap<>();
return maxPartitionsAfterOperations(s, 0, true, 0, k, mem) + 1;
}
// Returns the maximum number of partitions of s[i..n), where `canChange` is
// true if we can still change a letter, and `mask` is the bitmask of the
// letters we've seen.
private int maxPartitionsAfterOperations(final String s, int i, boolean canChange, int mask,
int k, Map<Long, Integer> mem) {
if (i == s.length())
return 0;
Long key = (long) i << 27 | (canChange ? 1 : 0) << 26 | mask;
if (mem.containsKey(key))
return mem.get(key);
// Initialize the result based on the current letter.
int res = getRes(s, i, canChange, mask, 1 << (s.charAt(i) - 'a'), k, mem);
// If allowed, explore the option to change the current letter.
if (canChange)
for (int j = 0; j < 26; ++j)
res = Math.max(res, getRes(s, i, false, mask, 1 << j, k, mem));
mem.put(key, res);
return res;
}
private int getRes(final String s, int i, boolean nextCanChange, int mask, int newBit, int k,
Map<Long, Integer> mem) {
final int nextMask = mask | newBit;
if (Integer.bitCount(nextMask) > k) // fresh start
return 1 + maxPartitionsAfterOperations(s, i + 1, nextCanChange, newBit, k, mem);
return maxPartitionsAfterOperations(s, i + 1, nextCanChange, nextMask, k, mem);
}
} // code provided by PROGIEZ
3003. Maximize the Number of Partitions After Operations LeetCode Solution in Python
class Solution:
def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
@functools.lru_cache(None)
def dp(i: int, canChange: bool, mask: int) -> int:
"""
Returns the maximum number of partitions of s[i..n), where `canChange` is
True if we can still change a letter, and `mask` is the bitmask of the
letters we've seen.
"""
if i == len(s):
return 0
def getRes(newBit: int, nextCanChange: bool) -> int:
nextMask = mask | newBit
if nextMask.bit_count() > k:
return 1 + dp(i + 1, nextCanChange, newBit)
return dp(i + 1, nextCanChange, nextMask)
# Initialize the result based on the current letter.
res = getRes(1 << (ord(s[i]) - ord('a')), canChange)
# If allowed, explore the option to change the current letter.
if canChange:
for j in range(26):
res = max(res, getRes(1 << j, False))
return res
return dp(0, True, 0) + 1 # code by PROGIEZ
