Partition Labels - Leetcode 763 - Python

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

leetcode 763

#neetcode #leetcode #python

[julianelmasry]

I know a legacy neetcode video when I see one

[xz]

Bro is so is just re-uploading old videos

[rostislav_xx]

I thought this is an interval problem. hahaha. I turned it into merge intervals type of problem since every char has st and end positions.

[shreyassunkad]

That was quick! Within 1 minute of daily challenge

[prathamchelaramani]

Very very excellent explaination, keep it up man.

[aayushtheapple]

Clean approach and code!
My approach was a bit different but it probably have better TC with single pass.
```python
class Solution:
def partitionLabels(self, s: str) -> List[int]:
minMaxIdx = defaultdict(list)
size = len(s)
for index, character in enumerate(s):
if not minMaxIdx[character]:
minMaxIdx[character] = [size, -1]
minIdx, maxIdx = minMaxIdx[character]
minMaxIdx[character] = [min(minIdx, index), max(maxIdx, index)]
blocks = [(val[0], val[1]) for key, val in minMaxIdx.items()]
blocks.sort()
res = [(-1, -1)]
for block in blocks:
start, end = block
prevEnd = res[-1][1]
if start > prevEnd:
res.append([start, end])
else:
res[-1][1] = max(prevEnd, end)

return [end-start+1 for start, end in res[1:]]
```

[biraj]

I used a similar idea, but instead of storing last index, having total occurence was more intuitive to me, but i used additional hashset:

class Solution:
def partitionLabels(self, s: str) -> List[int]:
# pretty straightforward
# keep track of all characters occcurence
# keep hash set to keep track of elements in the window
# append the window size when hash_set is empty.

counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1

l, r = 0, 0
hash_set = set()
ans = []
while r < len(s):
counter[s[r]] -= 1
hash_set.add(s[r])

if counter[s[r]] == 0:
hash_set.remove(s[r])

if not hash_set:
ans.append(r-l+1)
l = r+1
r += 1

return ans

[anupamtiwary]

Great, thanks.
I did it using merge overlapping intervals approach. It was costlier and lengthier.

[duttulurihitheshkumar]

I was able to solve this on my own but used up too much memory like a counter and a set. That too with some errors and after 2 iterations I got to the right solution. @NeetCodeIO, do you think this will get better with practice and time. I also want to ask is it fine if we do a mistake in calculations and get them right with a hint or in the second iteration?

[janszachno]

Today I managed to solve the daily myself :) Although my solution was n logn so there is room for improvement

[MrMikomi]

More exercises that 99.9% of devs will never do anything remotely similar to in their job.

[gabrielfonseca]

Thought this problem would be much more difficult due to the constraints and yesterday's problem

[yhbarve]

Turned this into a merge intervals problem. Slightly inefficient (although I got a 100% on LC) but more elegant.

[jotrades]

Chat am I too OP to convert this problem into a merge interval problem and then solve it 😁

[Thiccolo]

Do you think it's worth it to vibe code leetcode?