Partition Labels

🎯

Partition Labels

mediumGREEDYAmazonGoogleBloomberg

Imagine you have a string representing a sequence of tasks, and you want to split it into as many parts as possible so that each task appears in only one part, making scheduling easier.

💡 This problem requires understanding how to track the last occurrence of characters and greedily decide partitions. Beginners often struggle because it’s not obvious how to decide where to cut the string without missing future occurrences.

📋

Problem Statement

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of these parts.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters only

💡

Example

Input"ababcbacadefegdehijhklij"

Output[9,7,8]

The partitions are 'ababcbaca', 'defegde', 'hijhklij'. Each letter appears in only one partition.

• Single character string → [1]
• All characters unique → each character forms a partition of size 1
• All characters the same → one partition of size n
• String with repeated characters clustered at start and end → partitions adjusted accordingly

⚠️

Common Mistakes

Not updating partition end to max last occurrence

Partitions may be cut too early, causing repeated characters in multiple partitions

✅ Always update end = max(end, last occurrence of current character)

Using a map but not precomputing last occurrences

Repeated scanning causes timeouts

✅ Precompute last occurrences before partitioning

Off-by-one errors when calculating partition size

Incorrect partition sizes returned

✅ Use end - start + 1 for partition size

Not handling single character strings

Code may fail or return empty result

✅ Ensure loop and conditions handle length 1 correctly

Using find/indexOf inside loops in brute force

Causes TLE on large inputs

✅ Avoid repeated scanning by using last occurrence map

🧠

Brute Force (Check all partitions by scanning for overlaps)

💡 This approach exists to build intuition by trying all possible partitions and verifying if they satisfy the condition, though it is inefficient.

Intuition

Try every possible partition by scanning the string and checking if any character appears outside the current partition. If yes, extend the partition until all characters are contained.

Algorithm

1. For each possible partition start, try every possible partition end.
2. Check if all characters in this partition do not appear outside it.
3. If valid, record the partition size and move to the next partition start.
4. Repeat until the entire string is partitioned.

💡 This algorithm is hard to see because it involves nested loops and repeated scanning, which is inefficient but conceptually straightforward.

</>

Code

def partitionLabels(s):
    n = len(s)
    res = []
    i = 0
    while i < n:
        j = i
        seen = set()
        while j < n:
            seen.add(s[j])
            # Check if any character in seen appears beyond j
            valid = True
            for c in seen:
                if s.find(c, j + 1) != -1:
                    valid = False
                    break
            if valid:
                break
            j += 1
        res.append(j - i + 1)
        i = j + 1
    return res

# Driver code
if __name__ == '__main__':
    s = "ababcbacadefegdehijhklij"
    print(partitionLabels(s))

Line Notes

n = len(s)Calculate string length to control iteration

while i < n:Outer loop to start partitions from index i

seen = set()Track characters in current partition

for c in seen:Check if any character appears beyond current partition end

if s.find(c, j + 1) != -1:If character found beyond j, partition is invalid

res.append(j - i + 1)Add size of valid partition to result

i = j + 1Move to next partition start after current partition

import java.util.*;
public class PartitionLabels {
    public static List<Integer> partitionLabels(String s) {
        int n = s.length();
        List<Integer> res = new ArrayList<>();
        int i = 0;
        while (i < n) {
            int j = i;
            Set<Character> seen = new HashSet<>();
            while (j < n) {
                seen.add(s.charAt(j));
                boolean valid = true;
                for (char c : seen) {
                    if (s.indexOf(c, j + 1) != -1) {
                        valid = false;
                        break;
                    }
                }
                if (valid) break;
                j++;
            }
            res.add(j - i + 1);
            i = j + 1;
        }
        return res;
    }
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }
}

Line Notes

int n = s.length();Get string length for iteration control

while (i < n)Outer loop to find partitions starting at i

Set<Character> seen = new HashSet<>();Track characters in current partition

for (char c : seen)Check if character appears beyond current partition end

if (s.indexOf(c, j + 1) != -1)If character found beyond j, partition invalid

res.add(j - i + 1);Add partition size to result list

i = j + 1;Move to next partition start

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;

vector<int> partitionLabels(string s) {
    int n = s.size();
    vector<int> res;
    int i = 0;
    while (i < n) {
        int j = i;
        unordered_set<char> seen;
        while (j < n) {
            seen.insert(s[j]);
            bool valid = true;
            for (char c : seen) {
                // Manually check if c appears beyond j
                bool found = false;
                for (int k = j + 1; k < n; k++) {
                    if (s[k] == c) {
                        found = true;
                        break;
                    }
                }
                if (found) {
                    valid = false;
                    break;
                }
            }
            if (valid) break;
            j++;
        }
        res.push_back(j - i + 1);
        i = j + 1;
    }
    return res;
}

int main() {
    string s = "ababcbacadefegdehijhklij";
    vector<int> result = partitionLabels(s);
    for (int x : result) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

int n = s.size();Get string length for loop control

while (i < n)Outer loop to find partitions starting at i

unordered_set<char> seen;Track characters in current partition

for (char c : seen)Check if character appears beyond current partition end

// Manually check if c appears beyond jstd::string::find does not support start index; manual search needed

if (found)If character found beyond j, partition invalid

res.push_back(j - i + 1);Add partition size to result vector

i = j + 1;Move to next partition start

function partitionLabels(s) {
    const n = s.length;
    const res = [];
    let i = 0;
    while (i < n) {
        let j = i;
        const seen = new Set();
        while (j < n) {
            seen.add(s[j]);
            let valid = true;
            for (const c of seen) {
                if (s.indexOf(c, j + 1) !== -1) {
                    valid = false;
                    break;
                }
            }
            if (valid) break;
            j++;
        }
        res.push(j - i + 1);
        i = j + 1;
    }
    return res;
}

// Driver code
const s = "ababcbacadefegdehijhklij";
console.log(partitionLabels(s));

Line Notes

const n = s.length;Get string length for iteration control

while (i < n)Outer loop to find partitions starting at i

const seen = new Set();Track characters in current partition

for (const c of seen)Check if character appears beyond current partition end

if (s.indexOf(c, j + 1) !== -1)If character found beyond j, partition invalid

res.push(j - i + 1);Add partition size to result array

i = j + 1;Move to next partition start

⏱

Complexity

TimeO(n^2 * m) where m is average size of seen set (worst case O(n^3))

SpaceO(n) for result and seen set

Nested loops with inner scanning for each character cause cubic time in worst case

💡 For n=20, this means roughly 8000 operations, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem constraints and correctness.

🧠

Better Approach (Last Occurrence Map + Greedy Partitioning)

💡 This approach improves efficiency by precomputing last occurrences of characters and greedily extending partitions, avoiding repeated scans.

Intuition

Record the last index each character appears at. Then iterate through the string, extending the current partition's end to the farthest last occurrence of any character seen so far.

Algorithm

1. Create a map of each character to its last occurrence index.
2. Initialize start and end pointers for the current partition.
3. Iterate through the string, updating end to max(last occurrence of current char, current end).
4. When current index equals end, close the partition and record its size.
5. Move start to the next index after end and repeat.

💡 This algorithm is easier to understand once you grasp the idea of last occurrences dictating partition boundaries.

</>

Code

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

# Driver code
if __name__ == '__main__':
    s = "ababcbacadefegdehijhklij"
    print(partitionLabels(s))

Line Notes

last = {c: i for i, c in enumerate(s)}Precompute last occurrence of each character

start = 0Start index of current partition

end = 0End index of current partition, updated greedily

for i, c in enumerate(s)Iterate over string with index and character

end = max(end, last[c])Extend partition end to last occurrence of current character

if i == endIf current index reaches partition end, close partition

res.append(end - start + 1)Record size of partition

start = i + 1Move start to next partition

import java.util.*;
public class PartitionLabels {
    public static List<Integer> partitionLabels(String s) {
        Map<Character, Integer> last = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            last.put(s.charAt(i), i);
        }
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last.get(s.charAt(i)));
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }
}

Line Notes

Map<Character, Integer> last = new HashMap<>();Map to store last occurrence of each character

last.put(s.charAt(i), i);Update last occurrence for each character

int start = 0, end = 0;Initialize partition start and end

end = Math.max(end, last.get(s.charAt(i)));Extend partition end to last occurrence of current character

if (i == end)If current index reaches partition end, close partition

res.add(end - start + 1);Add partition size to result

start = i + 1;Move start to next partition

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

vector<int> partitionLabels(string s) {
    unordered_map<char, int> last;
    for (int i = 0; i < (int)s.size(); i++) {
        last[s[i]] = i;
    }
    vector<int> res;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i]]);
        if (i == end) {
            res.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

int main() {
    string s = "ababcbacadefegdehijhklij";
    vector<int> result = partitionLabels(s);
    for (int x : result) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

unordered_map<char, int> last;Map to store last occurrence of each character

last[s[i]] = i;Update last occurrence for each character

int start = 0, end = 0;Initialize partition start and end

end = max(end, last[s[i]]);Extend partition end to last occurrence of current character

if (i == end)If current index reaches partition end, close partition

res.push_back(end - start + 1);Add partition size to result vector

start = i + 1;Move start to next partition

function partitionLabels(s) {
    const last = new Map();
    for (let i = 0; i < s.length; i++) {
        last.set(s[i], i);
    }
    const res = [];
    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, last.get(s[i]));
        if (i === end) {
            res.push(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

// Driver code
const s = "ababcbacadefegdehijhklij";
console.log(partitionLabels(s));

Line Notes

const last = new Map();Map to store last occurrence of each character

last.set(s[i], i);Update last occurrence for each character

let start = 0, end = 0;Initialize partition start and end

end = Math.max(end, last.get(s[i]));Extend partition end to last occurrence of current character

if (i === end)If current index reaches partition end, close partition

res.push(end - start + 1);Add partition size to result array

start = i + 1;Move start to next partition

⏱

Complexity

TimeO(n)

SpaceO(1) since only 26 lowercase letters

Single pass to build last occurrence map and single pass to partition string

💡 For n=100000, this means about 200000 operations, efficient for large inputs.

Interview Verdict: Accepted / Optimal for interview coding

This approach is efficient and clean, suitable for coding in interviews.

🧠

Optimal Approach (Greedy with Array for Last Occurrence)

💡 This approach optimizes the previous by using a fixed-size array for last occurrences instead of a map, improving speed and memory.

Intuition

Since input is lowercase letters, use an array of size 26 to store last occurrences, then greedily partition as before.

Algorithm

1. Create an array last[26] to store last occurrence of each character.
2. Iterate over string to fill last array.
3. Iterate again to greedily extend partition end to max last occurrence.
4. When current index equals end, close partition and record size.
5. Move start to next index and repeat.

💡 This approach is the same logic as before but uses arrays for constant-time access.

</>

Code

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[ord(c) - ord('a')])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

# Driver code
if __name__ == '__main__':
    s = "ababcbacadefegdehijhklij"
    print(partitionLabels(s))

Line Notes

last = [0] * 26Initialize fixed-size array for last occurrences

last[ord(c) - ord('a')] = iStore last index for character c

start = 0Start index of current partition

end = 0End index of current partition

end = max(end, last[ord(c) - ord('a')])Extend partition end to last occurrence

if i == endClose partition when current index reaches end

res.append(end - start + 1)Add partition size

start = i + 1Move start to next partition

import java.util.*;
public class PartitionLabels {
    public static 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> res = 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) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }
}

Line Notes

int[] last = new int[26];Fixed-size array for last occurrences

last[s.charAt(i) - 'a'] = i;Store last index for character

int start = 0, end = 0;Initialize partition pointers

end = Math.max(end, last[s.charAt(i) - 'a']);Extend partition end

if (i == end)Close partition when current index reaches end

res.add(end - start + 1);Add partition size

start = i + 1;Move start to next partition

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> partitionLabels(string s) {
    int last[26] = {0};
    for (int i = 0; i < (int)s.size(); i++) {
        last[s[i] - 'a'] = i;
    }
    vector<int> res;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            res.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

int main() {
    string s = "ababcbacadefegdehijhklij";
    vector<int> result = partitionLabels(s);
    for (int x : result) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

int last[26] = {0};Fixed-size array for last occurrences

last[s[i] - 'a'] = i;Store last index for character

int start = 0, end = 0;Initialize partition pointers

end = max(end, last[s[i] - 'a']);Extend partition end

if (i == end)Close partition when current index reaches end

res.push_back(end - start + 1);Add partition size

start = i + 1;Move start to next partition

function partitionLabels(s) {
    const last = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        last[s.charCodeAt(i) - 97] = i;
    }
    const res = [];
    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, last[s.charCodeAt(i) - 97]);
        if (i === end) {
            res.push(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

// Driver code
const s = "ababcbacadefegdehijhklij";
console.log(partitionLabels(s));

Line Notes

const last = new Array(26).fill(0);Fixed-size array for last occurrences

last[s.charCodeAt(i) - 97] = i;Store last index for character

let start = 0, end = 0;Initialize partition pointers

end = Math.max(end, last[s.charCodeAt(i) - 97]);Extend partition end

if (i === end)Close partition when current index reaches end

res.push(end - start + 1);Add partition size

start = i + 1;Move start to next partition

⏱

Complexity

TimeO(n)

SpaceO(1) fixed array size

Same as previous approach but with faster constant time lookups

💡 This is the fastest practical approach for large inputs.

Interview Verdict: Accepted / Best practice

This is the recommended approach to implement in interviews for speed and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the last occurrence map greedy approach or its array optimization in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3) worst case	O(n)	No	Yes	Mention only - never code
2. Greedy with Map	O(n)	O(1) (26 letters)	No	Yes	Code this if allowed map usage
3. Greedy with Array	O(n)	O(1) fixed array	No	Yes	Best practice to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice explaining your approach clearly, and anticipate common pitfalls.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Introduce the last occurrence map and greedy approach for optimization.Discuss the array optimization for constant-time lookups.Write clean, readable code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force to greedy, and coding accuracy.

Common Follow-ups

• What if the input contains uppercase letters? → Adjust last occurrence mapping accordingly.
• Can you reconstruct the actual partitions? → Yes, by slicing the string using recorded partition boundaries.

💡 Follow-ups test your adaptability to input variations and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Need to partition or split a sequence; 2) Each element must appear in only one partition; 3) Overlapping intervals or last occurrences matter; 4) Greedy extension of partition boundaries is possible.

Signature Phrases

'partition the string into as many parts as possible''each letter appears in at most one part'

NOT This Pattern When

Problems requiring dynamic programming for subsequence optimization or problems where partitions can overlap.

Similar Problems

Split Array into Disjoint Intervals - similar partitioning logicMinimum Number of Arrows to Burst Balloons - greedy interval coverage

Practice

1. Given the following Python code for assigning cookies to children, what is the final returned value when g = [1, 2, 3] and s = [1, 1]?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace first iteration

   g and s sorted: g=[1,2,3], s=[1,1]. i=0, j=0, count=0. s[0]=1 ≥ g[0]=1 -> count=1, i=1, j=1.

2. Step 2: Trace second iteration

   i=1, j=1, count=1. s[1]=1 < g[1]=2 -> j=2. Loop ends as j=2 equals len(s).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only one cookie satisfies a child's greed [OK]

Hint: Trace pointer increments carefully [OK]

Common Mistakes:

• Counting cookies not sufficient for greed
• Off-by-one in loop conditions
• Ignoring pointer increments

2. Given the following code and input, what is the final returned total cost?

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))

easy

A. 110

B. 150

C. 120

D. 140

Solution

1. Step 1: Sort costs by difference cost[0] - cost[1]

   Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

2. Step 2: Assign first half to city A, rest to city B and sum costs

   First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by difference, assign first half to city A [OK]

Common Mistakes:

• Misordering after sorting by difference
• Off-by-one in loop boundary
• Adding wrong city cost for last half

3. What is the time complexity of the optimal greedy solution that sorts the greed and cookie arrays before assigning cookies to children?

medium

A. O(n + m) because sorting is not needed if arrays are scanned directly

B. O(n * m) where n is number of children and m is number of cookies

C. O(n log n + m log m) due to sorting both arrays, then O(n + m) for assignment

D. O(n^2) because each child is compared to all cookies in worst case

Solution

1. Step 1: Identify sorting costs

   Sorting greed array of size n costs O(n log n), sorting cookies array of size m costs O(m log m).

2. Step 2: Analyze assignment loop

   Two pointers scan both arrays once, costing O(n + m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates complexity, linear scan is minor [OK]

Hint: Sorting dominates; assignment is linear [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Ignoring sorting cost
• Confusing linear scan with quadratic

4. The following code attempts to form the largest number from a list of integers. Which line contains a subtle bug that causes incorrect output on inputs like [0, 0, 0]?

medium

A. Line 8: Returning concatenated string without zero check

B. Line 4-6: Custom comparator function

C. Line 7: Sorting with custom comparator

D. Line 3: Converting integers to strings

Solution

1. Step 1: Trace output for input [0,0,0]

   After sorting, nums_str is ['0', '0', '0'], concatenation is '000'.

2. Step 2: Identify missing check for all zeros

   Without checking if first element is '0', the function returns '000' instead of '0'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding a check to return '0' if nums_str[0] == '0' fixes the bug [OK]

Hint: Check if first string is '0' to handle all-zero case [OK]

Common Mistakes:

• Forgetting all-zero check
• Incorrect comparator logic
• Sorting without custom comparator

5. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?

hard

A. Sort both arrays and increment both pointers i and j on assignment as before

B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies

C. Sort greed array only and assign the largest cookie to each child without sorting cookies

D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

1. Step 1: Understand reuse effect

   Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

2. Step 2: Modify greedy accordingly

   Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Not incrementing j allows cookie reuse [OK]

Hint: Do not advance cookie pointer on assignment for reuse [OK]

Common Mistakes:

• Incrementing both pointers breaks reuse
• Using brute force unnecessarily
• Ignoring sorting leads to suboptimal matches