Skip to content
Katabench
Try free

String Compression

Easy About 10 min Free, no account needed

Run-length encode a string without quadratic string building.

The brief

Given a lowercase string s, return its run-length encoding: each maximal run of a repeated character becomes the character followed by the run length. "aabcccccaaa" becomes "a2b1c5a3".

The performance bar

The obvious approach appends to a plain string with += for every run; each append copies everything written so far, so many short runs cost O(n2). The hidden test alternates 100,000 characters (ababab...), maximizing the number of runs, so it's too slow. You need to build the output in amortized O(n).

Starter code

C#
using System;

public class Solution
{
    // TODO: return the run-length encoding: "aabcccccaaa" -> "a2b1c5a3".
    public string Compress(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 →

Related guides

What it practices

String processing
Parse, scan and match text character by character with correct edge cases.

Related katas