Skip to content

3233. Maximize The Number Of Partitions After Operations

String Dynamic Programming Bit Manipulation Bitmask

Problem - Maximize The Number Of Partitions After Operations

Hard

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        n = len(s)

        @cache
        def dfs(i: int, current: int, tmp: int) -> int:
            if i >= n:
                return 1
            val = 1 << (ord(s[i]) - ord('a'))

            next_val = current | val
            if next_val.bit_count() > k:
                result = dfs(i + 1, val, tmp) + 1
            else:
                result = dfs(i + 1, next_val, tmp)

            if tmp:
                for j in range(26):
                    next_val = current | (1 << j)
                    if next_val.bit_count() > k:
                        result = max(result, dfs(i + 1, 1 << j, 0) + 1)
                    else:
                        result = max(result, dfs(i + 1, next_val, 0))
            return result

        return dfs(0, 0, 1)

Submission Stats:

  • Runtime: 954 ms (37.93%)
  • Memory: 257.6 MB (31.03%)