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 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
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.
Related guides
What it practices
- String processing
- Parse, scan and match text character by character with correct edge cases.
Related katas
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Count Distinct Letters Easy Free How many different letters appear? A 26-slot array already knows.