#128 Medium Time O(n) Space O(1) Animated

Partition Labels

Partition string into as many parts as possible with unique characters.

LeetCode ↗

Approach: Greedy / Two Pointers

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Partition string into as many parts as possible with unique characters.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Greedy / Two Pointers

O(n) O(1)

def partitionLabels(s):
    lastIndex = {} # char -> last index in s
    for i, c in enumerate(s):
        lastIndex[c] = i
        
    res = []
    size, end = 0, 0
    for i, c in enumerate(s):
        size += 1
        end = max(end, lastIndex[c])
        
        if i == end:
            res.append(size)
            size = 0
            
    return res

Merge Triplets to Form Target Triplet

Valid Parenthesis String

Partition Labels

Steps

Description

Constraints

Tags

Solution — Greedy / Two Pointers