#763

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Partition Labels

Partition a string into maximal parts so that each letter appears in only one segment, using two-pointer scanning.

Problem Statement

Given a string s, partition it into as many parts as possible so that no letter appears in more than one part. Each partition must be contiguous, and concatenating all partitions should reconstruct the original string. Return a list of integers representing the sizes of these partitions.

For example, the string "ababcbacadefegdehijhklij" can be split into ["ababcbaca", "defegde", "hijhklij"], ensuring every letter appears in only one partition. Invalid splits would either repeat letters across partitions or create partitions smaller than the greedy maximum possible.

Examples

Example 1

Input: s = "ababcbacadefegdehijhklij"

Output: [9,7,8]

The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2

Input: s = "eccbbbbdec"

Output: [10]

Example details omitted.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

Solution Approach

Precompute last occurrences

Create a hash map storing the last index of each character. This allows the two-pointer scan to know how far each partition must extend to include all instances of its letters.

Two-pointer greedy scan

Use a start and end pointer. Iterate through the string, updating the end pointer to the maximum last occurrence of characters seen. When the current index reaches end, record the partition size and move start to the next index.

Collect partition sizes

Each time the end pointer is reached, compute the partition size as end - start + 1, append it to the result list, and advance the start pointer to continue scanning the remaining string. This ensures maximal partitions without overlap.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(k)

Time complexity is O(n) since each character is scanned once. Space complexity is O(k) where k is the number of unique lowercase letters, used for the hash map storing last occurrences.

What Interviewers Usually Probe

Check if the candidate tracks last indices efficiently using a hash map.
Watch for correct handling of greedy expansion of partitions without missing characters.
Notice if candidate avoids unnecessary repeated scans of the same characters.

Common Pitfalls or Variants

Common pitfalls

Failing to update the end pointer correctly when a character's last occurrence is beyond current end.
Splitting partitions too early, causing repeated letters in multiple segments.
Assuming contiguous letters must be grouped by first appearance only, ignoring last occurrence.

Follow-up variants

Partition a string where each letter can appear at most twice instead of once, adjusting partition expansion accordingly.
Return the actual substring partitions instead of sizes, requiring careful slice management during two-pointer scan.
Handle uppercase and lowercase letters distinctly while maintaining maximal partitioning logic.

FAQ

What pattern does Partition Labels follow?

It follows a two-pointer scanning pattern with invariant tracking, expanding partitions to include the last occurrence of all letters seen.

Why is a hash map needed in Partition Labels?

The hash map stores last occurrences of characters, allowing the end pointer to expand correctly for maximal partitions.

Can Partition Labels be solved without a greedy approach?

A naive solution might repeatedly scan for repeated letters, but greedy two-pointer scanning ensures O(n) efficiency.

What are common mistakes when implementing Partition Labels?

Common errors include splitting too early, missing last occurrences, or not tracking end pointer updates.

How does GhostInterview optimize Partition Labels solving?

GhostInterview guides the candidate through last-index tracking, greedy partition expansion, and validation of partition sizes for correctness.

terminal

Solution

Solution 1: Greedy

We first use an array or hash table $\textit{last}$ to record the last occurrence of each letter in the string $s$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        mx = j = 0
        ans = []
        for i, c in enumerate(s):
            mx = max(mx, last[c])
            if mx == i:
                ans.append(i - j + 1)
                j = i + 1
        return ans

Continue Practicing

#767 reorganize string #942 di string match #567 permutation in string