Bird
Raised Fist0

Which line contains the subtle bug that can cause incorrect partitions?

medium🐞 Bug Identification Q7 of Q15
Greedy Algorithms - Partition Labels
Consider this buggy code snippet for Partition Labels. Which line contains the subtle bug that can cause incorrect partitions? ```python def partitionLabels(s): last = {c: i for i, c in enumerate(s)} res = [] start = 0 end = 0 for i, c in enumerate(s): end = last[c] # Line X if i == end: res.append(end - start + 1) start = i + 1 return res ```
ALine X: end = last[c] should use max(end, last[c])
BLine 2: last occurrence map should be a list, not dict
CLine 7: res.append should append i - start instead of end - start + 1
DLine 9: start should be set to i instead of i + 1
Step-by-Step Solution
Solution:
  1. Step 1: Understand partition end update

    Partition end must be the max last occurrence of all characters seen so far.
  2. Step 2: Identify bug

    Line X overwrites end with last[c], ignoring previous max, causing premature partitioning.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Using max(end, last[c]) fixes the bug [OK]
Quick Trick: Partition end must be max of last occurrences [OK]
Common Mistakes:
MISTAKES
  • Overwriting end instead of max
  • Miscomputing partition lengths
  • Incorrect start index update
Trap Explanation:
PITFALL
  • Candidates often miss that end must be extended to max last occurrence, not reset.
Interviewer Note:
CONTEXT
  • Tests bug spotting in greedy partitioning logic.
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