Longest Substring After At Most K Character Replacements

Medium20–25 min

Topics

StringSliding WindowHash Table

Companies

AmazonGoogleFacebookBloomberg

Given a string s and an integer k, return the length of the longest substring that can be turned into one repeated character by changing at most k of its characters. A window of length L is achievable with at most k replacements exactly when L - maxFreq ≤ k, where maxFreq is the count of the window's most frequent character — every other character in the window is the one that would need replacing. The sliding window technique grows the window right while tracking a frequency count and the running maxFreq, and shrinks from the left by one whenever that condition breaks. maxFreq is allowed to go stale after a shrink — it never causes an invalid window to be accepted, since the tracked answer only advances when a genuinely longer valid window is found — so the whole scan still runs in O(n).

Test Case 1:

Input:s = "aabcb", k = 1

Output:3

Explanation:Replace the 'c' in "bcb" (or the odd one out in "aab") and the run reaches length 3.

Test Case 2:

Input:s = "abab", k = 2

Output:4

Explanation:Replacing both 'b' characters with 'a' turns the whole string into "aaaa".

Test Case 3:

Input:s = "aaaa", k = 0

Output:4

Explanation:No replacements are allowed, but the string is already one repeated character.

Constraints

◆1 ≤ s.length ≤ 10⁵
◆0 ≤ k ≤ s.length
◆s consists of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase) — 2-10 lowercase lettersk — 0 to s.length

1	class Solution {
2	public int longestSubstringAfterKReplacements(String s, int k) {
3	int[] count = new int[26];
4	int left = 0, maxFreq = 0, maxLen = 0;
5	for (int right = 0; right < s.length(); right++) {
6	count[s.charAt(right) - 'a']++;
7	maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'a']);
8	if ((right - left + 1) - maxFreq > k) {
9	count[s.charAt(left) - 'a']--;
10	left++;
11	}
12	maxLen = Math.max(maxLen, right - left + 1);
13	}
14	return maxLen;
15	}
16	}
17

Variables

left0

maxFreq0

maxLen0

INITIALIZE

Start left, maxFreq, and maxLen all at 0, with an empty 26-letter frequency count.

Step 1 / 14

Approach & Solutions

Brute Force

Brute

For every possible starting index, grow the window to the right — tracking a 26-letter frequency count and the count of its most frequent character — until replacing every other character in the window would need more than k replacements, then record the window's length. Correct, but every start re-scans from scratch, throwing away everything the previous start already discovered.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestSubstringAfterKReplacements(String s, int k) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] count = new int[26];
            int maxFreq = 0;
            int j = i;
            while (j < s.length()) {
                count[s.charAt(j) - 'a']++;
                maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'a']);
                if ((j - i + 1) - maxFreq > k) break;
                j++;
            }
            maxLen = Math.max(maxLen, j - i);
        }
        return maxLen;
    }
}

Optimal — Sliding Window

Optimal

Grow the window by moving right and tracking a frequency count of the characters inside it, along with the count of its most frequent character seen so far. A window of length L is achievable with at most k replacements exactly when L - maxFreq ≤ k (every character except the most frequent one gets replaced). Whenever that's violated, shrink from the left by one. The window's size only ever grows or holds steady, so its largest size along the scan is the answer.

TimeO(n)