Partition Labels - Leetcode 763 - Python

0:00 - Read the problem
2:28 - Drawing Explanation
11:34 - Coding Explanation

leetcode 763

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[aleksanderdukaczewski]

Today I got invited for an interview with Facebook, thank you so much for your videos, especially DP!

[darthvadar]

Man you’re so good, I don’t even have to get to the end of the video to grasp the algorithm. Well done

[srinadhp]

As usual, you made a very "hard-to-understand" problem look very easy! Thanks again!

[MethyleneBlue]

My first instinct was to approach this problem as I did “merge intervals, ” with the main difference being that I have to create the intervals based on each character’s last index. After that, instead of merging the intervals, just return their respective upper bound indices.

[FifaHades]

It is not easy to come up with this algorithm in half an hour, great work.

[BbB-vruh]

Spent 45 minutes trying this one last night. When I stopped I was super close to a working solution, which is a good sign. I’m glad to see I had the same conceptual solution by the end of my attempt at this problem as what this video showed at least.

[sumishajmani]

@NeetCode: I added this condition and the runtime jumped to 90% while space complexity less than 85%.

if end==len(s)-1 and sum(res)!=len(s):
res.append(len(s)-sum(res))
break

[aaronhanson]

neetcode: "so you might be starting to get an idea how to solve this problem"
me: haha funny joke.

[chetanraghavv]

Great!
I could come up with a NlogN approach which was using merging overlapping intervals but this is amazing.

[lenzvital]

You are a life saver, keep being Neet!

[kumarshikhar]

We can also create intervals for each character in the string, where interval start is the first index of occurrence of character and interval end is the last index of occurrence of character. Then just merge intervals which is already a solved problem "Merge Intervals"

[rohitsai]

Wow. Beautiful explanation! Keep up the good work man.

[lianchen]

FB on site interview next Monday. Thanks for your video series.

[gattuso]

Just solved the problem at the middle of the video. Thanks, boss

[theedmaster]

Good idea, it is interesting to see how much you can shorten it, mine is the same in time/space complexity but maybe double the lines 🤣

[jkk-gc]

This is the question I stared at for 10 minutes and just gave up. Greedy questions are the trickiest. I feel like it's very hard to solve if you haven't solved a similar question before.

[anujapuranik]

Thankyou again for your explanation. These videos are really helpful and they are helping people like us study!!

[chaitanyayeole]

I did this using two hash maps and a single for loop.
One hash map to save which characters are in the current partitions and another to save the count of all the characters.

class Solution:
def partitionLabels(self, s: str) -> List[int]:
count = Counter(s)
current_partition = {}
result = []
l = 0


for r in range(len(s)):
current_partition[s[r]] = 1
count[s[r]] -= 1

if count[s[r]] == 0:
del current_partition[s[r]]

if not current_partition:
result.append(r - l + 1)
l = r + 1

continue

return result

This is giving me good time complexity but memory complexity is too bad. Can this be improved, where just the logic of hash map is changed?

@NeetCode

[ahmetcemek]

How is the space complexity of this question is O(1)? Don't we use extra memory by creating a hashmap so shouldn't be O(N)?

[Tamnguyen-zkby]

Could just use a regular int[] rather than a hashmap to keep track of your end position... endPos[c-'a'] = i