Partition Labels

---

Intuition

• For each letter, it must partake in the entire subarray from the first occurrence of itself to the last occurrence of itself.
• If in between its own first and last occurrence, there is another letter encountered whose last occurrence surpasses the last occurring of the previous letters, then the subarray must be longer, since not making the subarray longer would mean the letter leading up to the last occurrence of what came previously would be part of two subarrays.
• So, greedily select subarrays based on the last occurring instance in between the first and last occurrence of the index you are currently on.

Complexity

Runtime

$O(N)$ since we only ever iterate through N elements total.

Space

$O(N)$ due to hashmap

Code

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        n = len(s)
        hm = {}
        for i, c in enumerate(s):
            hm[c] = i
 
        i = 0
        res = []
        while i < n:
            max_end = hm[s[i]]
            j = i
            while j <= max_end:
                max_end = max(max_end, hm[s[j]])
                j += 1
 
            res.append(max_end - i + 1)
            i = max_end + 1
 
        return res

Notes

Cards

START Basic Front: Partition Labels Back: Keep track of the last occurring character in between the first and last occurring of the index you are on. END

---

References

• Partition Labels