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
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 = 2Output
3Changing
s[2] to b makes s become "acbca", which is partitioned as "ac", "bc", and "a", for a total of 3 partitions.Example 2
Input
s = "aabaab", k = 3Output
1Initially
s contains 2 distinct characters, so any one-character change still leaves the whole string with at most 3 distinct characters as the longest prefix, resulting in 1 partition.Constraints
- 1 <= s.length <= 10^4
- s consists only of lowercase English letters.
- 1 <= k <= 26