Special Binary String

Description

You are given a string s made up of lowercase English letters. Your task is to split this string into as many parts as possible, with one important constraint: each letter must appear in at most one part.

In other words, if a letter (say 'a') appears in one partition, then every occurrence of 'a' in the entire string must be inside that same partition. No letter is allowed to straddle two different partitions.

After partitioning, concatenating all the parts in order must give back the original string s.

Return a list of integers representing the size (length) of each partition, in order.

Examples

Example 1

Input: s = "ababcbacadefegdehijhklij"

Output: [9, 7, 8]

Explanation: The partition is "ababcbaca", "defegde", "hijhklij". Each letter appears in exactly one part:

Part 1 ("ababcbaca"): contains letters a, b, c — and none of these appear in parts 2 or 3.
Part 2 ("defegde"): contains letters d, e, f, g — none appear elsewhere.
Part 3 ("hijhklij"): contains letters h, i, j, k, l — none appear elsewhere.
This is the maximum number of partitions possible.

Example 2

Input: s = "eccbbbbdec"

Output: [10]

Explanation: The entire string forms a single partition. The letter 'e' appears at positions 0 and 8, 'c' appears at positions 1 and 9, forcing these distant positions into the same partition. Once those ranges overlap, every character in between must also belong to the same partition, resulting in one partition of size 10.

Example 3

Input: s = "ababccd"

Output: [4, 2, 1]

Explanation: The partition is "abab", "cc", "d".

'a' appears at indices 0 and 2 — both inside "abab".
'b' appears at indices 1 and 3 — both inside "abab".
'c' appears at indices 4 and 5 — both inside "cc".
'd' appears only at index 6 — alone in "d".
Three partitions is the maximum: we cannot split "abab" further because 'a' and 'b' each appear twice, binding indices 0–3 together.

Constraints

1 ≤ s.length ≤ 500
s consists of lowercase English letters only.

Editorial

Brute Force

Intuition

To create a valid partition, every occurrence of a character must lie within the same part. So when we start building a partition from a given position, we need to ensure it extends far enough to include the last occurrence of every character we encounter along the way.

The most straightforward way to do this: for each character in the current partition, scan the rest of the string to find where that character appears for the last time. If the last occurrence is beyond our current partition boundary, we must extend the partition to include it. This extension might reveal new characters whose last occurrences are even further ahead, so we keep expanding until the boundary stabilizes.

Imagine you're sorting physical letter tiles into boxes. You pick up the first tile 'a' and must put every other 'a' tile in the same box. While gathering those 'a' tiles, you also pick up 'b' tiles that happen to be in between. Now you need to gather all remaining 'b' tiles too, which might pull in even more tiles.

The brute-force aspect is that for each character, we scan the string to find its last occurrence, doing repeated linear scans instead of precomputing this information.

Step-by-Step Explanation

Let's trace through with s = "ababccd":

Step 1: Start a partition at index 0. Set end = 0. Process character at index 0: 'a'.

Scan the string rightward to find the last 'a' → found at index 2.
Extend end to 2. The partition must now cover at least [0, 2].

Step 2: Process character at index 1: 'b'.

Scan the string rightward to find the last 'b' → found at index 3.
Extend end to 3. The partition must now cover at least [0, 3].

Step 3: Process character at index 2: 'a'.

Scan rightward for last 'a' → no 'a' found after index 2.
end remains 3.

Step 4: Process character at index 3: 'b'.

Scan rightward for last 'b' → no 'b' found after index 3.
end remains 3. We've reached i = end = 3. Partition complete!
Record partition "abab", size = 4.

Step 5: Start new partition at index 4. Set end = 4. Process 'c' at index 4.

Scan rightward for last 'c' → found at index 5.
Extend end to 5.

Step 6: Process 'c' at index 5. Scan rightward — no 'c' after index 5. end remains 5. i = end = 5. Partition complete!

Record partition "cc", size = 2.

Step 7: Start new partition at index 6. Process 'd' at index 6. Scan rightward — no 'd' after index 6. end = 6 = i. Partition complete immediately.

Record partition "d", size = 1.

Result: [4, 2, 1]

Brute Force — Scanning for Last Occurrences On-The-Fly — Watch how we build each partition by scanning the string to find the last occurrence of each character, extending the partition boundary each time a character's reach goes further.

Algorithm

Initialize start = 0 and an empty result list
While start < n:
a. Set end = start (minimum partition boundary)
b. Set i = start
c. While i ≤ end:
- For character s[i], scan the string from right to left to find its last occurrence
- If the last occurrence is beyond end, extend end to that position
- Increment i
  d. Record partition size: end - start + 1
  e. Move start to end + 1 for the next partition
Return the result list

Code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> result;
        int start = 0;
        int n = s.size();
        
        while (start < n) {
            int end = start;
            int i = start;
            while (i <= end) {
                // Scan rightward to find last occurrence of s[i]
                for (int j = n - 1; j > i; j--) {
                    if (s[j] == s[i]) {
                        end = max(end, j);
                        break;
                    }
                }
                i++;
            }
            result.push_back(end - start + 1);
            start = end + 1;
        }
        
        return result;
    }
};

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        result = []
        start = 0
        n = len(s)
        
        while start < n:
            end = start
            i = start
            while i <= end:
                # Scan rightward to find last occurrence of s[i]
                for j in range(n - 1, i, -1):
                    if s[j] == s[i]:
                        end = max(end, j)
                        break
                i += 1
            result.append(end - start + 1)
            start = end + 1
        
        return result

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int start = 0;
        int n = s.length();
        
        while (start < n) {
            int end = start;
            int i = start;
            while (i <= end) {
                // Scan rightward to find last occurrence of s.charAt(i)
                for (int j = n - 1; j > i; j--) {
                    if (s.charAt(j) == s.charAt(i)) {
                        end = Math.max(end, j);
                        break;
                    }
                }
                i++;
            }
            result.add(end - start + 1);
            start = end + 1;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each character in the string, we potentially scan the entire string to find its last occurrence. In the worst case (e.g., a string with one partition covering all characters), every character triggers a full rightward scan. With n characters and O(n) scan per character, the total is O(n²).

Space Complexity: O(1)

Aside from the output list, we only use a few integer variables (start, end, i, j). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force wastes time by repeatedly scanning the string to find last occurrences. Every time we encounter a character, we search from right to left through potentially the whole string. If a character appears 50 times, we perform 50 separate scans to keep rediscovering the same last-occurrence position.

With n up to 500, O(n²) = 250,000 operations is still feasible, but the approach is inelegant and does redundant work. The critical observation is:

The last occurrence of each character never changes. It's a fixed property of the input string. We can compute it once upfront in a single pass, store it in a lookup table, and then retrieve it in O(1) for every subsequent query.

This transforms the expensive "scan the string" operation into an instant lookup, collapsing the O(n²) double loop into a clean O(n) single pass.

Optimal Approach - Greedy with Precomputed Last Occurrences

Intuition

The key insight is that for each character, its last occurrence position in the string is a fixed value we can precompute. Once we know this, building partitions becomes a simple greedy scan.

Think of it this way: when you start reading a partition and see the letter 'a' at position 0, you look up where 'a' last appears — say position 8. Now you know this partition must extend at least to position 8. But as you walk from 0 to 8, you encounter other letters like 'b' whose last occurrence might be at position 5 (already covered) or 'c' whose last occurrence is at position 7 (also covered). You keep updating the "farthest point we must reach" as you go.

The magic moment happens when your current position catches up to the farthest point. At that instant, you know that every character you've seen in this partition has its last occurrence within the partition. You can safely cut here and start a fresh partition.

It's like walking down a hallway where each doorway has a sign saying "the last room with this key is room X." You must walk to the farthest room sign you see. Once you arrive there and no sign points further ahead, you've collected all the keys for this wing and can start a new one.

The algorithm has two phases:

Build a map: One pass to record the last occurrence index of every character.
Greedy scan: One pass through the string, maintaining the farthest boundary and cutting whenever the current index reaches it.

Step-by-Step Explanation

Let's trace with s = "ababccd":

Phase 1 — Precompute last occurrences (single pass):

Scan "ababccd": last['a'] = 2, last['b'] = 3, last['c'] = 5, last['d'] = 6

Phase 2 — Greedy partition (single pass):

Step 1: i = 0, char = 'a'. Look up last['a'] = 2. Update end_max = max(0, 2) = 2.

end_max = 2 ≠ i = 0. Not at boundary yet. Continue.

Step 2: i = 1, char = 'b'. Look up last['b'] = 3. Update end_max = max(2, 3) = 3.

end_max = 3 ≠ i = 1. The boundary got pushed further because 'b' appears later. Continue.

Step 3: i = 2, char = 'a'. Look up last['a'] = 2. Update end_max = max(3, 2) = 3.

end_max = 3 ≠ i = 2. The 'a' didn't push the boundary further (its last occurrence is already inside). Continue.

Step 4: i = 3, char = 'b'. Look up last['b'] = 3. Update end_max = max(3, 3) = 3.

end_max = 3 == i = 3. Boundary reached! Every character in [0, 3] has its last occurrence within this range.
Record partition size: 3 - 0 + 1 = 4. Start next partition at index 4.

Step 5: i = 4, char = 'c'. Look up last['c'] = 5. Update end_max = max(0, 5) = 5.

end_max = 5 ≠ i = 4. Continue.

Step 6: i = 5, char = 'c'. Look up last['c'] = 5. Update end_max = max(5, 5) = 5.

end_max = 5 == i = 5. Boundary reached! Partition size: 5 - 4 + 1 = 2.

Step 7: i = 6, char = 'd'. Look up last['d'] = 6. Update end_max = max(0, 6) = 6.

end_max = 6 == i = 6. Boundary reached immediately! Partition size: 6 - 6 + 1 = 1.

Result: [4, 2, 1]

Greedy Partitioning with Precomputed Last Occurrences — Watch the single-pass greedy scan: for each character, we instantly look up its last occurrence (O(1) via the precomputed map) and extend the partition boundary. When the scan position reaches the boundary, the partition is complete.

Algorithm

Precompute last occurrences: Iterate through the string once. For each character, record its index. Since later indices overwrite earlier ones, you end up with the last occurrence of each character.
Initialize: start = 0, end_max = 0, result = []
Greedy scan: For each index i from 0 to n-1:
a. Look up the last occurrence of s[i], call it last_i
b. Update end_max = max(end_max, last_i)
c. If end_max == i:
- A partition boundary is found
- Append partition size (i - start + 1) to result
- Set start = i + 1 for the next partition
Return result

Code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26] = {};
        int n = s.size();
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i;
        }
        
        vector<int> result;
        int start = 0, endMax = 0;
        
        for (int i = 0; i < n; i++) {
            endMax = max(endMax, last[s[i] - 'a']);
            if (endMax == i) {
                result.push_back(i - start + 1);
                start = i + 1;
            }
        }
        
        return result;
    }
};

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

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        
        List<Integer> result = new ArrayList<>();
        int start = 0, endMax = 0;
        
        for (int i = 0; i < s.length(); i++) {
            endMax = Math.max(endMax, last[s.charAt(i) - 'a']);
            if (endMax == i) {
                result.add(i - start + 1);
                start = i + 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make exactly two passes through the string:

First pass (precomputation): Iterate through all n characters to build the last-occurrence map. Each character is processed in O(1). Total: O(n).
Second pass (greedy scan): Iterate through all n characters. For each character, we do one O(1) hash map lookup and one O(1) comparison. Total: O(n).

Combined: O(n) + O(n) = O(n).

Space Complexity: O(1)

The last-occurrence map stores at most 26 entries (one per lowercase English letter). This is a constant that does not grow with input size. The result list is part of the output and is not counted as auxiliary space. All other variables (start, end_max, i) are constant space.

This is a significant improvement from the O(n²) brute force, achieved by the simple insight of precomputing information that was being redundantly recomputed.