MediumPythonJavaScriptTypeScript
Greedy — Partition Labels
AlgorithmsGreedyStrings
solve(s) — split the string s into as many parts as possible so that **each
letter appears in at most one part. Return the sizes** of the parts, in order.
Record the last index of every letter, then sweep: extend the current part to
the farthest last-index of any letter seen so far. When the sweep reaches that
index, the part is complete.
Examples
solve("ababcbacadefegdehijhklij") → [9,7,8]
solve("eccbbbbdec") → [10]
solve("a") → [1]
solve("abc") → [1,1,1]
solve("caedbdedda") → [1,9]Sample tests
Test #1Classic example
Input: ["ababcbacadefegdehijhklij"]
Output: [9,7,8]
Test #2Cannot be split
Input: ["eccbbbbdec"]
Output: [10]
Test #3Single letter
Input: ["a"]
Output: [1]