Partition Labels

📋

Problem

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.

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

Edge cases: Single character string → [1]All characters unique → each character forms a partition of size 1All characters the same → one partition of size n

</>

IDE

def partitionLabels(s: str) -> list:public List<Integer> partitionLabels(String s)vector<int> partitionLabels(string s)function partitionLabels(s)

def partitionLabels(s):
    # Write your solution here
    pass

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<int> partitionLabels(string s) {
    // Write your solution here
    return {};
}

function partitionLabels(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,1,1,1,1]Incorrectly splitting partitions at every character without considering last occurrences.✅ Use a map to track last occurrence of each character and extend partition end to max last occurrence.

Wrong: [9,7,7]Off-by-one error in partition size calculation (missing +1).✅ Calculate partition size as end_index - start_index + 1.

Wrong: [1,8,7,8]Greedy trap: splitting partitions too early without extending to last occurrence of all characters.✅ Update partition end to max last occurrence of all characters seen so far before splitting.

Wrong: [9,7]Overlapping partitions due to misunderstanding partition constraints; characters appear in multiple partitions.✅ Ensure partitions are disjoint by using last occurrence boundaries to split.

Wrong: Timeout or crash on large inputUsing brute force or nested loops causing O(n^2) or worse complexity.✅ Implement O(n) solution using last occurrence map and single pass greedy partitioning.

✓

Test Cases

Try testing your code on empty and single-character strings to catch base case bugs.

Consider tricky inputs that expose greedy mistakes or boundary errors.

Focus on algorithmic complexity; large inputs require O(n) solutions.

t1_01basic

Input{"s":"ababcbacadefegdehijhklij"}

Expected[9,7,8]

⏱ Performance - must finish in 2000ms

The partitions are 'ababcbaca' (length 9), 'defegde' (length 7), and 'hijhklij' (length 8). Each letter appears in only one partition.

💡 Track the last occurrence of each character to know partition boundaries.

💡 Use a greedy approach to extend the current partition to the farthest last occurrence of any character seen so far.

💡 When the current index reaches the partition end, record the partition size and start a new partition.

Why it failed: Incorrect partition sizes indicate failure to track last occurrences or extend partitions properly. Fix by updating partition end to max last occurrence of characters seen.

✓ Correctly partitions string using last occurrence map and greedy extension.

t1_02basic

Input{"s":"eccbbbbdec"}

Expected[10]

⏱ Performance - must finish in 2000ms

All characters overlap in the string, so only one partition of size 10 is possible.

💡 Check if any character's last occurrence extends beyond current partition end.

💡 If yes, extend the partition end accordingly.

💡 If partition end reaches the string end, return the entire string length as one partition.

Why it failed: Failing to extend partition end to cover all last occurrences causes premature partitioning. Fix by updating partition end to max last occurrence.

✓ Correctly identifies single partition covering all characters.

t2_01edge

Input{"s":""}

Expected[]

⏱ Performance - must finish in 2000ms

Empty string input results in no partitions.

💡 Consider what the output should be when input is empty.

💡 Check if your code handles zero-length strings without errors.

💡 Return an empty list immediately if string length is zero.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding base case for empty string returning [].

✓ Handles empty input gracefully with empty output.

t2_02edge

Input{"s":"z"}

Expected[1]

⏱ Performance - must finish in 2000ms

Single character string forms one partition of size 1.

💡 Check behavior when string length is 1.

💡 Partition should be the entire string length.

💡 Return [1] for single character input.

Why it failed: Fails to handle single character input correctly, returning empty or wrong size. Fix by returning [len(s)] when length is 1.

✓ Correctly returns single partition of size 1 for single character input.

t2_03edge

Input{"s":"abcde"}

Expected[1,1,1,1,1]

⏱ Performance - must finish in 2000ms

All characters unique, so each character forms its own partition of size 1.

💡 Check if your code handles all unique characters correctly.

💡 Each character's last occurrence is its own index.

💡 Partitions should be single characters each.

Why it failed: Incorrectly merges unique characters into fewer partitions. Fix by ensuring partition ends at last occurrence of current character.

✓ Correctly partitions each unique character separately.

t2_04edge

Input{"s":"aaaaaa"}

Expected[6]

⏱ Performance - must finish in 2000ms

All characters are the same, so only one partition of size 6.

💡 Check if your code handles repeated identical characters.

💡 Last occurrence of the character is at the end of the string.

💡 Partition should cover entire string.

Why it failed: Fails to extend partition to last occurrence of repeated character. Fix by updating partition end to last occurrence of character.

✓ Correctly returns one partition covering all identical characters.

t3_01corner

Input{"s":"abacbdade"}

Expected[8,1]

⏱ Performance - must finish in 2000ms

Greedy trap: naive greedy splitting at first repeated character fails; entire string must be one partition.

💡 Beware of greedy approaches that split too early at repeated characters.

💡 Use last occurrence map to extend partition end correctly.

💡 Partition end must be max last occurrence of all characters seen so far.

Why it failed: Greedy trap: splitting partition too early without considering last occurrences. Fix by tracking max last occurrence and extending partition end accordingly.

✓ Avoids greedy trap by correctly extending partition to cover all character occurrences.

t3_02corner

Input{"s":"abcdecfghijjklmn"}

Expected[1,1,4,1,1,1,1,2,1,1,1,1]

⏱ Performance - must finish in 2000ms

Off-by-one error: partitions are 'abcdec' (6) and 'fghijjklmn' (9).

💡 Check partition boundaries carefully to avoid off-by-one errors.

💡 Partition size = end index - start index + 1.

💡 Ensure partition end index is inclusive.

Why it failed: Off-by-one error in partition size calculation. Fix by adding +1 when computing partition length.

✓ Correctly calculates partition sizes with inclusive end indices.

t3_03corner

Input{"s":"abacbdadefegdehijhklij"}

Expected[14,8]

⏱ Performance - must finish in 2000ms

Confusion between 0/1 partitioning: partitions must be disjoint and cover all characters exactly once.

💡 Ensure partitions are disjoint and cover all characters exactly once.

💡 Use last occurrence map to avoid overlapping partitions.

💡 Do not reuse characters in multiple partitions.

Why it failed: Incorrect overlapping partitions due to misunderstanding partition constraints. Fix by ensuring partitions are disjoint using last occurrence boundaries.

✓ Correctly partitions string into disjoint segments covering all characters once.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000 tests O(n) solution efficiency; brute force O(n^2) would time out.

💡 Use O(n) approach with last occurrence map and greedy partitioning.

💡 Avoid nested loops or repeated scanning of string.

💡 Precompute last occurrences and iterate once to build partitions.

Why it failed: TLE due to O(n^2) or worse complexity. Fix by implementing O(n) greedy approach using last occurrence map.

✓ Efficient O(n) solution passes within time limit.

Practice

1. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A simple greedy approach that always jumps to the farthest reachable index from the current position.

B. A breadth-first search (BFS) treating each index as a node and exploring all reachable indices level by level.

C. A dynamic programming approach that computes the minimum jumps for each index by checking all previous indices.

D. A depth-first search (DFS) exploring all possible jump sequences recursively and returning the minimum.

Solution

1. Step 1: Understand problem as shortest path in graph

   Each index can be seen as a node with edges to reachable indices. BFS explores nodes level by level, guaranteeing the shortest path (minimum jumps).

2. Step 2: Compare approaches

   Greedy alone can fail on some inputs by making locally optimal but globally suboptimal jumps. DP is correct but less efficient. DFS is exponential time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS ensures minimum jumps by level order traversal [OK]

Hint: Minimum jumps = shortest path -> BFS [OK]

Common Mistakes:

• Believing greedy always yields minimum jumps
• Confusing DP with BFS for this problem
• Assuming DFS is efficient here

2. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?

easy

A. 534330

B. 53430

C. 534303

D. 534330

Solution

1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

   We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

   Concatenate to get '534330'. The check for leading zero is false since first is '5'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation order matches expected largest number [OK]

Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]

Common Mistakes:

• Off-by-one in sorting
• Ignoring leading zero case
• Misordering '30' and '3'

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. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved

5. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), and you want to generate a string of length n with no two adjacent characters the same. Which modification to the max heap approach is necessary to handle this variant correctly?

hard

A. No change needed; the original heap approach works as is for infinite reuse

B. Track only the last used character and pick any other character from the set for the next position

C. Use a queue instead of a heap to cycle through characters ensuring no adjacency

D. Remove frequency counts and always push characters back immediately after use to allow reuse

Solution

1. Step 1: Understand infinite reuse implication

   Since characters can be reused infinitely, frequency counts are irrelevant; characters must be available again immediately after use.

2. Step 2: Modify heap usage

   Remove frequency decrement logic and always push characters back immediately after use to allow reuse while avoiding adjacency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Immediate pushback enables infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means no frequency decrement [OK]

Common Mistakes:

• Assuming original approach works unchanged
• Using queue without frequency logic
• Ignoring adjacency constraints