10038. Maximize the Number of Partitions After Operations

10038. Maximize the Number of Partitions After Operations

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        s=[ord(c)-ord('a') for c in s]
        @cache
        def dp(idx,left,seen):
            if idx==len(s):return 0

            ss=seen | (1<<s[idx])
            bc=ss.bit_count()
            if bc>k:
                ret=1+dp(idx+1,left,1<<s[idx])
            else:
                ret=dp(idx+1,left,ss)
            
            if left:
                for i in range(26):
                    ss=seen|(1<<i)
                    bc=ss.bit_count()
                    if bc>k:
                        ret=max(ret,1+dp(idx+1,left-1,1<<i))
                    else:
                        ret=max(ret,dp(idx+1,left-1,ss))
            return ret
        return dp(0,1,0)+1

1<<s[idx]相当于划分了

这里@cache相当于直接数组dp了

最后+1是因为最后一个划分一直没有算上，注意bc>k的时候之前才进行了计算