10038. Maximize the Number of Partitions After Operations | Weekly Leetcode 379
Segment Tree Series - bit.ly/segment-trees
*************************************************
Contest Link - leetcode.com/contest/weekly-c...
Problem Link - leetcode.com/contest/weekly-c...
A different approach (recursion) - leetcode.com/problems/maximiz...
*************************************************
Timestamps -
00:00 - Agenda
00:33 - Problem Description
04:00 - Brute force solution
06:35 - What all we need to optimise the solution?
12:45 - [ # of partitions starting at index "i" ] - Brute force solution
14:07 - [ # of partitions starting at index "i" ] - Optimising solution
20:20 - [ # of partitions starting at index "i" ] - Pseudo code
21:38 - [ # of partitions starting at index "i" ] - Time Complexity
22:50 - # of distinct elements in (l, r)
27:05 - Recap of the complete Algorithm
32:15 - Dry run of the Algorithm
39:35 - Code Walkthrough
*************************************************
Interview Experiences Playlists -
Microsoft - • Microsoft Interview Qu...
Amazon - • Amazon Interview Quest...
D.E.Shaw - • D.E.Shaw Interview Que...
Linkedin - • Linkedin Interview Que...
Facebook - • Facebook (Meta) Interv...
*********************************************************************
Please show support and subscribe if you find the content useful.
Пікірлер: 12
Your explanation is very nice
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?
Your videos are helping a lot! Thank you!
great brother you explain every bit so well
Hey,, I didn't quite understand what are we doing after we change a character to something else
would be great if you can make a video explaining why recursive solution fits constraints. No one in the solutions really explained it well.
Your way of explaining the soln is tooo goood
Bro, how did you find that it will be easy to optimise N, rather than optimising 26.N
If catastrophe was a question
Why don't you use bit manipulation to find the distinct character I think it will save the space and time more.
@codingmohan
6 ай бұрын
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
6 ай бұрын
@@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