LC-0763 Medium LeetCode

763. Partition Labels

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 81% Topics: Hash Table, Two Pointers, String, Greedy

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Strings 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        lookup = {c: i for i, c in enumerate(S)}
        first, last = 0, 0
        result = []
        for i, c in enumerate(S):
            last = max(last, lookup[c])
            if i == last:
                result.append(i-first+1)
                first = i+1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT