Bird
Raised Fist0

Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?

easy🧾 Code Trace Q12 of Q15
Greedy Algorithms - Partition Labels
Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?
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
A[10]
B[9, 1]
C[1, 9]
D[3, 7]
Step-by-Step Solution
Solution:
  1. Step 1: Compute last occurrences

    Characters: e last at 8, c last at 9, b last at 6, d last at 7.
  2. Step 2: Trace partitions

    Start=0, end=0 initially. Iterate: - i=0 (e): end=max(0,8)=8 - i=1 (c): end=max(8,9)=9 - i=2 (c): end=9 - i=3 (b): end=max(9,6)=9 - i=4 (b): end=9 - i=5 (b): end=9 - i=6 (b): end=9 - i=7 (d): end=max(9,7)=9 - i=8 (e): end=9 - i=9 (c): i==end, partition size=9-0+1=10 Append 10, start=10 (end of string) But since string length is 10, only one partition of size 10. However, careful: last occurrence of 'e' is 8, 'c' is 9, so partition ends at 9. So only one partition of size 10.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Partition covers entire string length 10 [OK]
Quick Trick: Track max last occurrence to find partition end [OK]
Common Mistakes:
MISTAKES
  • Miscounting partition size by off-by-one
  • Stopping partition too early ignoring max last occurrence
  • Confusing character indices
Trap Explanation:
PITFALL
  • Off-by-one errors or not updating partition end cause wrong partition sizes.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute greedy partitioning code.
Master "Partition Labels" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes