10038. Maximize the Number of Partitions After Operations | Weekly Leetcode 379

[@riteshmangdare]

Your explanation is very nice

[@syedsohaibuddin1375]

Your videos are helping a lot! Thank you!

[@saurabhthakur4952]

great brother you explain every bit so well

[@mukeshkumar-hy7yc]

Your way of explaining the soln is tooo goood

[@AnatoliySokolov-pb2bo]

would be great if you can make a video explaining why recursive solution fits constraints. No one in the solutions really explained it well.

[@rockingbadshah1848]

To do ( bottom up dp)

[@hrithikkumar7974]

when we try all possibility for start index of any segment and if it becomes equal to the previous segment's ending char then no of segments before the start of current segment will change because current start index will then become part of previous segment .Would that not cause any problem?

[@addictedgamerclashofclansa1251]

Hey,, I didn't quite understand what are we doing after we change a character to something else

[@josephaj8310]

Bro, how did you find that it will be easy to optimise N, rather than optimising 26.N

[@tommyshelby6277]

If catastrophe was a question

[@amitbajpai6265]

Why don't you use bit manipulation to find the distinct character I think it will save the space and time more.

[@codingmohan]

How will you do that with bit manipulation? The bitwise OR of the mask will help in finding distinct elements in a prefix but as you can't find bitwise OR of a range (L, R) given the bitwise OR of (0, L) and (0, R), I don't think we can find that without using a range query data structures like Segment Trees. Having said that using segment tree will take 0(logN) time which is slightly better then 0(26). Do you have any reference code so that I can understand bitwise solution a bit more?

[@AnatoliySokolov-pb2bo]

@@codingmohan Here's a Python DP Solution I wrote after looking at bitmask solutions. Idea is basically you store a bitmask for the letters that you have seen currently, and also use index and if you have changed a letter yet. Then for every index if your bitmask has more 1's than k you start a new mask. Thing I really don't get though about this dp solution is how its not a TLE since you can have 2^26 combos of masks if a mask is 26 bits and 10^4 or something indices but yet it runs pretty fast. I'm thinking its something about not being able to actually have every possible mask since n is only 10^4 but I'm not sure. Here's Python code, its pretty straightforward. class Solution: def maxPartitionsAfterOperations(self, s: str, k: int) -> int: masks = {} for char in s: if char not in masks: masks[char] = 1 k: res = 1 + dp(idx + 1, masks[s[idx]], can_change) else: res = dp(idx + 1, new_mask, can_change) if can_change: for i in range(26): new_mask = mask | (1 k: res = max(res,1 + dp(idx + 1, 1