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 code and input arrays, what is the final output printed?

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return -1
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

A = [3,5,1,2]
B = [3,6,3,3]
print(minDominoRotations(A, B))

easy

A. -1

B. 2

C. 1

D. 3

Solution

1. Step 1: Check candidate x = A[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.

2. Step 2: Check candidate x = B[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.
   Both candidates fail, so output is -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both candidates fail at i=1, so no solution [OK]

Hint: Check both candidates carefully for early failure [OK]

Common Mistakes:

• Assuming first candidate always works
• Miscounting rotations when both sides match

2. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

3. Identify the bug in the following code snippet for Two City Scheduling:

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: abs(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

medium

A. Sorting by absolute difference instead of signed difference

B. Incorrect calculation of n as half the length

C. Adding cost[1] for the first half instead of cost[0]

D. Using enumerate instead of a simple for loop

Solution

1. Step 1: Analyze sorting key

   The code sorts by absolute difference abs(cost[0] - cost[1]) instead of signed difference cost[0] - cost[1].

2. Step 2: Effect of wrong sorting

   Sorting by absolute difference loses the direction of cost preference, causing suboptimal assignments and higher total cost.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Signed difference sorting is required for correct greedy assignment [OK]

Hint: Sort by signed difference, not absolute [OK]

Common Mistakes:

• Sorting by absolute difference
• Miscounting half the people
• Swapping city costs in assignment

4. Suppose the Jump Game problem is modified so that you can jump backward as well as forward (i.e., jumps can be negative or positive). Which of the following approaches correctly determines if you can reach the last index from the first index under this new constraint?

hard

A. Use the original greedy approach tracking max reachable index, ignoring backward jumps

B. Use a breadth-first search (BFS) or graph traversal to explore all reachable indices including backward jumps

C. Use dynamic programming with memoization to recursively check reachability from each index

D. Sort the array and apply binary search to find reachable indices efficiently

Solution

1. Step 1: Understand the impact of backward jumps

   Backward jumps mean the problem is no longer monotonic; maxReach tracking fails as reachable indices can decrease.

2. Step 2: Identify suitable approach

   BFS or graph traversal explores all reachable indices in any direction, correctly handling negative jumps.

3. Step 3: Explain why other options fail

   Greedy fails due to backward jumps; DP recursion is possible but less efficient; sorting is irrelevant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS explores all reachable nodes regardless of jump direction [OK]

Hint: Backward jumps break greedy; BFS needed to explore all reachable indices [OK]

Common Mistakes:

• Trying to apply greedy despite backward jumps
• Assuming sorting helps reachability

5. Suppose the problem changes: you can reuse indices multiple times (cycles allowed). Which modification to the BFS approach ensures correct minimum jumps without infinite loops?

hard

A. Remove the visited set to allow revisiting indices for better paths.

B. Keep the visited set but reset it after each BFS level to allow revisits in next level.

C. Keep the visited set as is to prevent revisiting and infinite loops.

D. Use a distance array to track minimum jumps to each index and update it if a shorter path is found.

Solution

1. Step 1: Understand cycles and revisits

   Allowing reuse means indices can be revisited, so visited set alone blocks better paths.

2. Step 2: Use distance array for shortest paths

   Tracking minimum jumps per index and updating when a shorter path is found prevents infinite loops and finds optimal jumps.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses pruning; keeping visited blocks revisits.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Distance array with updates handles cycles correctly [OK]

Hint: Distance array needed when revisits allowed [OK]

Common Mistakes:

• Removing visited set causing infinite loops
• Resetting visited incorrectly
• Assuming original BFS works unchanged