Partition Labels - Practice Coding Problems

Partition Labels - Problem

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Input & Output

Example 1 — Basic Partitioning

$ Input: s = "ababcbaca"

› Output: [4,5]

💡 Note: The string can be partitioned into "abab" and "cbaca". The first partition contains all 'a' and 'b' characters, while the second contains all 'c' characters and remaining 'a's.

Example 2 — Simple Case

$ Input: s = "eccbbbbdec"

› Output: [10]

💡 Note: All characters appear throughout the string, so we cannot partition it further. The entire string must be one partition of length 10.

Example 3 — Maximum Partitions

$ Input: s = "abcdef"

› Output: [1,1,1,1,1,1]

💡 Note: Each character appears only once, so we can partition into 6 parts, each containing exactly one character.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters that may repeat

Find Partitions

Each letter must appear in exactly one partition

Output Sizes

Return the size of each partition

Key Takeaway

🎯 Key Insight: Track the furthest last occurrence position to determine where each partition can safely end

Asked in

a Amazon 45 G Google 35 f Facebook 28 M Microsoft 22

The key insight is to track the last occurrence of each character and greedily extend partitions until we can safely make a cut. The optimal approach uses a greedy strategy with hash map preprocessing. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Hash Map	O(n)	O(1)	First pass to find last occurrences, second pass to create partitions
Greedy Approach	O(n)	O(1)	Greedily extend partitions to the furthest required position
Brute Force - Try All Partitions	O(2ⁿ × n²)	O(n)	Generate all possible partitions and check validity

Two-Pass Hash Map — Algorithm Steps

First pass: Record last occurrence index of each character
Second pass: Track the furthest end position needed for current partition
When current position reaches the furthest end, complete the partition

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Record last occurrence of each character

Second Pass

Track furthest end needed for current partition

Create Partitions

Split when we reach the furthest required end

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 500
#define max(a, b) ((a) > (b) ? (a) : (b))

int* solution(char* s, int* returnSize) {
    int len = strlen(s);
    
    // First pass: record last occurrence of each character
    int lastOccurrence[26];
    for (int i = 0; i < 26; i++) {
        lastOccurrence[i] = -1;
    }
    for (int i = 0; i < len; i++) {
        lastOccurrence[s[i] - 'a'] = i;
    }
    
    // Second pass: determine partition boundaries
    int* partitions = (int*)malloc(len * sizeof(int));
    int partitionCount = 0;
    int start = 0;
    int end = 0;
    
    for (int i = 0; i < len; i++) {
        // Extend current partition to include last occurrence of current char
        end = max(end, lastOccurrence[s[i] - 'a']);
        
        // If we've reached the end of current partition
        if (i == end) {
            partitions[partitionCount++] = i - start + 1;
            start = i + 1;
        }
    }
    
    *returnSize = partitionCount;
    return partitions;
}

int main() {
    char s[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int returnSize;
    int* result = solution(s, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two linear passes through the string

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 lowercase letters

✓ Linear Space

269.4K Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler