Leet Code Solution : Weekly Contest : 10038. Maximize the Number of Partitions After Operations

Problem Statement

You are given a 0-indexed string s and an integer k.

You are to perform the following partitioning operations 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.
Before the operations, you are allowed to change at most one index in s to another lowercase English letter.

Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one index to change.

Intuition

The problem involves maximizing the number of partitions after certain operations. We need to decide when to change a character to achieve the maximum partitions. The use of dynamic programming with memorization helps in efficiently exploring different possibilities.

Approach

We can use dynamic programming with memorization to solve this problem. The states of the dynamic programming will include the current index, the set of characters seen between the start of the partition and index i, and whether the change condition is used or not. To save the set of characters, we can use a bitmask.

At each index i, we have two choices:

1. If adding the current character leads to surpassing the threshold of k, we create a new partition starting from index i.
2. Otherwise, we add the character at index i to the current set of characters.

Additionally, we have the option to exercise a character change at index i. We can choose between characters 'a' to 'z', specifically those characters that are not already in the current character set.

The dynamic programming function dfs explores the possibilities recursively, memorizing the results to avoid redundant computations.

Complexity

• Time complexity:

The time complexity of this solution is O(n∗2^k), where n is the length of the string s and k is the given integer. The dynamic programming function explores all possible combinations of characters and their changes.

• Space complexity:

The space complexity is O(n∗2^k), where n is the length of the string s and k is the given integer. This is due to the memorization table used to store intermediate results.

Code

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:

        dp={}

        def dfs(index,char_bitmask=0,change_used=0):
            nonlocal k
            if index>=len(s):
                return 1
            
            if (index,char_bitmask,change_used) in dp:
                return dp[(index,char_bitmask,change_used)]

            val=0
            bitmask_cur_char = 1<<(ord(s[index])-ord("a"))

            if (char_bitmask|bitmask_cur_char).bit_count()>k:
                val=max(val,1+dfs(index+1,bitmask_cur_char,change_used))
            else:
                val=max(val,dfs(index+1,char_bitmask|bitmask_cur_char,change_used))

            if change_used==0:

                for i in range(26):
                    bitmask_brute_char = 1<<i
                    if bitmask_brute_char & char_bitmask:
                        continue
                    if (char_bitmask|bitmask_brute_char).bit_count()>k:
                        val=max(val,1+dfs(index+1,bitmask_brute_char,1))
                    else:
                        val=max(val,dfs(index+1,char_bitmask|bitmask_brute_char,1))

            dp[(index,char_bitmask,change_used)]=val

            return dp[(index,char_bitmask,change_used)]

        return dfs(0)

References

1. LeetCode Solution — Dynamic Programming and Bit Manipulation
2. LeetCode Submission — 1139229578

🌟 Shoutout to ChatGPT’s Incredible Writing Partner! 🌟