Longest Repeating Character Replacement
Medium About 20 min Free, no account needed
Longest uniform run you can create with k character replacements.
The brief
Given a string s of uppercase letters and an integer k, you may replace at
most k characters. Return the length of the longest substring consisting of
one repeated letter you can produce.
A window qualifies when windowLength - mostFrequentLetterInWindow <= k. The
obvious approach re-counts letter frequencies for every window it tries, O(n2). The
hidden test is a 40,000-character string whose best window spans nearly all of
it, so it's too slow. You will need a solution that runs in O(n).
Starter code
using System;
public class Solution
{
// TODO: return the longest one-letter run achievable with at most k replacements.
public int CharacterReplacement(string s, int k)
{
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
- Sliding window
- Grow and shrink a contiguous range while maintaining its state incrementally.
Related katas
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Fruit Into Baskets Medium Free Longest stretch of trees using at most two fruit types.
- Minimum Size Subarray Sum Medium Free The shortest window of positive numbers reaching a target sum.
- Longest Rising Streak Easy Free Measure a consecutive telemetry climb without rescanning every possible starting point.