Partition Labels
Medium About 20 min Free, no account needed
Cut a string into the most pieces so no letter spans two pieces.
The brief
Given a string s, split it into as many parts as possible so that each
letter appears in at most one part, and return the list of part sizes (in
order).
The obvious approach re-scans the string to find each letter's last occurrence at every
position, O(n2). The hidden test runs on a 208,000-character string built from
thirteen equal parts, so each letter's last occurrence sits far from where you are
standing and every rescan travels a long way - in either direction, and whether you
hand-roll the scan or call LastIndexOf. You will need an approach that runs in
close to O(n).
Starter code
using System;
using System.Collections.Generic;
public class Solution
{
// TODO: return the sizes of the maximal cuts such that no letter appears in two cuts.
public int[] PartitionLabels(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
- Intervals and sweep lines
- Sort or sweep interval boundaries, including difference arrays for range updates.
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Integer to Roman Medium Free Write Roman numerals the way Romans did - greedily.
- Minimum Forward Jumps Medium Free Cross a jump array with the fewest hops, including dead ends, without enumerating every reachable edge.