Skip to main content
CodePeetCodePeet
CodePeet 250

Partition Labels

MEDIUMProblemSolveExternal Links

Description

You are given a string s. Your task is to partition this string into as many parts as possible such that each letter appears in at most one part.

After partitioning, when you concatenate all the parts in order, the result must equal the original string s.

Return a list of integers representing the size of each part.

For instance, the string "ababcc" can be split into ["abab", "cc"] because the letter a only appears in the first part and c only appears in the second part. However, ["aba", "bcc"] would be invalid because b appears in both parts.

Examples

Example 1

Input: s = "ababcbacadefegdehijhklij"

Output: [9, 7, 8]

Explanation: The string is partitioned into three parts: "ababcbaca", "defegde", and "hijhklij".

  • The first part "ababcbaca" contains letters a, b, c. None of these letters appear anywhere in the remaining string "defegdehijhklij".
  • The second part "defegde" contains letters d, e, f, g. None of these appear in the third part.
  • The third part "hijhklij" contains letters h, i, j, k, l. These don't appear in the earlier parts.

This partition maximizes the number of parts — splitting further (e.g., into 4 parts) is impossible without a letter spanning two parts.

Example 2

Input: s = "eccbbbbdec"

Output: [10]

Explanation: Every letter in this string (e, c, b, d) appears at various positions throughout. For example, 'e' appears at indices 0 and 9, 'c' at indices 1 and 9, etc. No matter where we try to cut, at least one letter would span two parts. Therefore, the entire string must be a single partition of size 10.

Constraints

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

Editorial

Brute Force

Intuition

Imagine you are reading a book and want to split it into chapters, but you have a rule: every word that appears in a chapter cannot appear in any other chapter. You start reading from the first word. You look at the word and ask: where is the very last time this word appears in the entire book? Your chapter must extend at least that far. As you keep reading within this chapter, each new word might push the chapter boundary even further.

The simplest approach does exactly this, but without any preparation. Each time we encounter a character, we scan the entire string from the end backwards to locate where that character last appears. We then extend our current partition boundary to include that position. When we have scanned up to the boundary, the partition is complete.

The problem with this approach is that we may scan for the same character multiple times. If 'b' appears 5 times in the partition, we end up doing 5 separate full-string scans for 'b', each time finding the same answer. This redundant work makes the approach slower than necessary.

Step-by-Step Explanation

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

Step 1: Initialize: start = 0, end = 0. We begin building the first partition.

Step 2: i = 0, char = 'a'. Scan the entire string right-to-left to find the last 'a' → found at index 8. Update end = max(0, 8) = 8. The partition must extend to at least index 8.

Step 3: i = 1, char = 'b'. Scan the string for the last 'b' → found at index 5. end = max(8, 5) = 8. No change since 5 < 8.

Step 4: i = 2, char = 'a'. Scan the entire string for 'a' AGAIN → found at index 8. end stays 8. This is the first redundant scan — we already found 'a' at index 8 in Step 2.

Step 5: i = 4, char = 'c'. Scan for last 'c' → index 7. end stays 8.

Step 6: i = 5, char = 'b'. Scan for last 'b' AGAIN → index 5. end stays 8. Another redundant scan — we already knew this from Step 3.

Step 7: i = 8. We've reached i == end (8 == 8). All characters in [0, 8] have their final occurrences within this range. First partition complete: "ababcbaca", size = 9.

Step 8: New partition starts at index 9. i = 9, char = 'd'. Scan for last 'd' → index 14. end = 14.

Step 9: i = 10, char = 'e'. Scan for last 'e' → index 15. end = max(14, 15) = 15. The boundary extends because 'e' appears beyond index 14.

Step 10: i = 15. i == end (15 == 15). Second partition complete: "defegde", size = 7.

Step 11: New partition at index 16. Processing h (last = 19), i (last = 22), j (last = 23). End boundary expands from 19 to 22 to 23.

Step 12: i = 23. i == end. Third partition: "hijhklij", size = 8.

Step 13: Return [9, 7, 8].

Brute Force — Scanning for Last Occurrences On The Fly — Watch how each character triggers a full string scan to find its last occurrence, leading to redundant work when the same character is encountered again.

Algorithm

  1. Initialize start = 0, end = 0, and an empty result list
  2. Iterate through each index i in the string:
    • For character s[i], scan the entire string from the end backwards to find the last position where s[i] appears
    • Update end = max(end, last_position)
    • If i == end:
      • A partition is found: add end - start + 1 to result
      • Set start = end + 1
      • Reset end = start
  3. Return the result list

Code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> result;
        int start = 0, end = 0;
        
        for (int i = 0; i < s.size(); i++) {
            // Scan entire string for last occurrence of s[i]
            int lastPos = i;
            for (int j = s.size() - 1; j > i; j--) {
                if (s[j] == s[i]) {
                    lastPos = j;
                    break;
                }
            }
            end = max(end, lastPos);
            
            if (i == end) {
                result.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
};
class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        result = []
        start = 0
        end = 0
        
        for i in range(len(s)):
            # Scan entire string for last occurrence of s[i]
            last_pos = i
            for j in range(len(s) - 1, i, -1):
                if s[j] == s[i]:
                    last_pos = j
                    break
            end = max(end, last_pos)
            
            if i == end:
                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, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Scan entire string for last occurrence of s.charAt(i)
            int lastPos = i;
            for (int j = s.length() - 1; j > i; j--) {
                if (s.charAt(j) == s.charAt(i)) {
                    lastPos = j;
                    break;
                }
            }
            end = Math.max(end, lastPos);
            
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n characters in the string, we perform a scan of up to n characters to find its last occurrence. In the worst case (e.g., a string of all the same character), every position triggers a full reverse scan. Total: n positions × O(n) scan per position = O(n²).

Space Complexity: O(1)

We use only a few integer variables (start, end, loop counters). The result list is not counted as extra space since it is part of the output. No additional data structures are created.

Why This Approach Is Not Efficient

The brute force approach works correctly but performs redundant work. Each time we encounter a character, we scan the entire string to find its last occurrence — even if we already scanned for that same character earlier. For a string like "aaaaaaa...", we would scan for 'a' at every single position, each time getting the same answer.

With n up to 500, O(n²) = 250,000 operations, which is manageable for this problem's constraints. However, the approach is conceptually wasteful and would not scale to larger inputs.

The key insight is: the last occurrence of each character is fixed and never changes. We can compute it once upfront in O(n) time and then look it up in O(1) for each position. This eliminates all redundant scanning and reduces the total work from O(n²) to O(n).

Optimal Approach - Greedy with Precomputed Last Occurrences

Intuition

Think of it like planning road trips on a highway with labeled rest stops. Before you start driving, you look at the map and mark the position of each rest stop's farthest branch (its last occurrence). Now when you drive, you know exactly how far each stop's territory extends without needing to scout ahead.

The optimal approach works in two clean passes:

Pass 1 (Preparation): Scan the string once and record the last index where each character appears. Store this in a small lookup table (at most 26 entries for lowercase English letters).

Pass 2 (Greedy Partitioning): Walk through the string from left to right. Maintain a variable end that tracks how far the current partition must extend. For each character at position i, look up its last occurrence in O(1) and update end if needed. When i catches up to end, the current partition is complete — every character within has its last occurrence inside this range.

By separating the precomputation from the scanning, we eliminate all redundant work. Each character's last occurrence is computed exactly once, and every lookup during the greedy scan is O(1).

Step-by-Step Explanation

Let's trace with s = "ababcbacadefegdehijhklij":

Step 1: Precompute last occurrences in one pass: a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21.

Step 2: Initialize start = 0, end = 0, result = [].

Step 3: i = 0, char = 'a'. O(1) lookup: last['a'] = 8. end = max(0, 8) = 8. The partition must reach at least index 8.

Step 4: i = 1, char = 'b'. last['b'] = 5. end = max(8, 5) = 8. No change — 'b' is already within our boundary.

Step 5: i = 4, char = 'c'. last['c'] = 7. end stays 8. Characters a, b, c all have last occurrences ≤ 8.

Step 6: i = 8, char = 'a'. last['a'] = 8. i == end (8 == 8)! Partition found. Size = 8 - 0 + 1 = 9. Add 9 to result.

Step 7: start = 9. i = 9, char = 'd'. last['d'] = 14. end = max(9, 14) = 14.

Step 8: i = 10, char = 'e'. last['e'] = 15. end = max(14, 15) = 15. Boundary expands!

Step 9: i = 13, char = 'g'. last['g'] = 13. end stays 15. All intermediate characters fit within [9, 15].

Step 10: i = 15, char = 'e'. i == end (15 == 15)! Second partition found. Size = 15 - 9 + 1 = 7.

Step 11: start = 16. i = 16, char = 'h'. last['h'] = 19. end = 19.

Step 12: i = 17, char = 'i'. last['i'] = 22. end = max(19, 22) = 22. Extends.

Step 13: i = 18, char = 'j'. last['j'] = 23. end = max(22, 23) = 23. Extends to the very end.

Step 14: i = 23. i == end (23 == 23)! Third partition found. Size = 23 - 16 + 1 = 8.

Step 15: Return [9, 7, 8].

Greedy Partition — Precomputed Last Occurrences Enable O(1) Lookups — Watch how precomputing the last occurrence of each character allows us to instantly determine partition boundaries without redundant scanning.

Algorithm

  1. Precompute last occurrences: Iterate through the string once. For each character, record its index. Since later indices overwrite earlier ones, the final value is the last occurrence.
  2. Initialize: start = 0, end = 0, result = []
  3. Greedy scan: For each index i from 0 to n-1:
    • Look up last[s[i]] in O(1)
    • Update end = max(end, last[s[i]])
    • If i == end:
      • Partition found: append end - start + 1 to result
      • Set start = end + 1
  4. Return result

Code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // Step 1: Precompute last occurrence of each character
        int last[26] = {};
        for (int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }
        
        // Step 2: Greedy partitioning
        vector<int> result;
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                result.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
};
class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        # Step 1: Precompute last occurrence of each character
        last = {}
        for i, c in enumerate(s):
            last[c] = i
        
        # Step 2: Greedy partitioning
        result = []
        start = 0
        end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                result.append(end - start + 1)
                start = end + 1
        
        return result
class Solution {
    public List<Integer> partitionLabels(String s) {
        // Step 1: Precompute last occurrence of each character
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        
        // Step 2: Greedy partitioning
        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make exactly two passes through the string. The first pass (precomputing last occurrences) visits each of the n characters once, performing an O(1) hash map insertion. The second pass (greedy scan) also visits each character once, performing an O(1) lookup and comparison. Total: 2n operations = O(n).

Space Complexity: O(1)

The last-occurrence lookup table stores at most 26 entries (one per lowercase English letter). Since 26 is a constant independent of the input size n, the extra space is O(26) = O(1). The result list is part of the output and is not counted as extra space.