Problem Statement in English

You’re given a string s. Your task is to split the string into as many substrings as possible, ensuring that each unique character from the input string only appears in one substring atmost, and return the length of each substring as a list.

Approach

As we progress through the string, we need to keep track of the last occurrence of each character. If that index is less than or equal to the current index, we can safely add the length of the substring to our result list.

So we do a spot of preprocessing to create a hashmap of the last occurrence of each character in the string. Then we can use a max heap to keep track of the maximum index of the characters we’ve seen so far.

Solution in Python


class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hm = defaultdict(int)

        for i, char in enumerate(s):
            hm[char] = i

        maxheap = []
        res = []

        prev = 0
        seen = set()
        for i, char in enumerate(s):
            if char not in seen:
                heappush(maxheap, -hm[char])
                seen.add(char)

            if -maxheap[0] <= i:
                res.append(i - prev + 1)
                prev = i + 1

        return res

Complexity

  • Time: $O(nlogn)$
    Since we pop from the heap at most $n$ times, and each pop takes $O(logn)$ time, the overall time complexity is $O(nlogn)$.

  • Space: $O(1)$
    Since the hashmap we use can store upto $n$ key-value pairs (assuming that every character in the string is unique), but since there can only be 26 possible unique characters, this may also be considered $O(1)$.

And we are done.