Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

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