763. Partition Labels - Explanation

Description

You are given a string s consisting of lowercase english letters.

We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.

Return a list of integers representing the size of these substrings in the order they appear in the string.

Example 1:

Input: s = "xyxxyzbzbbisl"

Output: [5, 5, 1, 1, 1]

Explanation: The string can be split into ["xyxxy", "zbzbb", "i", "s", "l"].

Example 2:

Input: s = "abcabc"

Output: [6]

Constraints:

1 <= s.length <= 100

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in the string s.

Hint 1

A character has a first and last index in the given string. Can you think of a greedy approach to solve this problem? Maybe you should try iterating over one of these two indices.

Hint 2

We store the last index of each character in a hash map or an array. As we iterate through the string, treating each index as a potential start of a partition, we track the end of the partition using the maximum last index of the characters seen so far in the current partition. Additionally, we maintain the size of the current partition using a variable, say size.

Hint 3

We update the end of the current partition based on the maximum last index of the characters, extending the partition as needed. When the current index reaches the partition’s end, we finalize the partition, append its size to the output list, reset the size to 0, and continue the same process for the remaining string.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Two Pointers (Greedy)

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastIndex = {}
        for i, c in enumerate(s):
            lastIndex[c] = i

        res = []
        size = end = 0
        for i, c in enumerate(s):
            size += 1
            end = max(end, lastIndex[c])

            if i == end:
                res.append(size)
                size = 0
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique characters in the string $s$ .