Longest Substring With Replacement

Tags: sliding window

Problem Statement:
You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Intuition:
We want the longest substring that can become all one character after at most k changes.
Think of it as a sliding window:

• Inside the window, the “majority character” should dominate.
• If window_size - maxFreq > k, it means we’d need more than k changes → shrink the window.
• Otherwise, the window is valid → expand it.
  We track the maximum valid window size.
  Key trick: keep maxFreq as the maximum count ever seen (don’t lower it when shrinking), because window size naturally limits correctness.

Code:

Brute Force

Go through all the possible substring and check where they are valid substring or not according to the given condition. that is for a substring st - len(st) - max(freq of st_i) <= k. If yes update the maxLen

def characterReplacement(self, s: str, k: int) -> int:
	maxLen = 0
	for l in range(len(s)):
		for r in range(l+1, len(s)):
			mp = {}
			maxFreq = 0
			for i in range(l, r+1):
				mp[s[i]] = mp.get(s[i], 0) + 1
			maxFreq = max(maxFreq, mp[s[i]])
			substrLen = r - l + 1
			if substrLen - maxFreq <= k:
			maxLen = max(maxLen, substrLen)
	return maxLen

Semi Brute Force

Same as above but we do not need a extra loop of single element mapping

def characterReplacement(self, s: str, k: int) -> int:
	maxLen = 0
		for l in range(len(s)):
			mp = {}
			maxFreq = 0
			mp[s[l]] = 1
			for r in range(l+1, len(s)):
				mp[s[r]] = mp.get(s[r], 0) + 1
				maxFreq = max(maxFreq, mp[s[r]])
				substrLen = r - l + 1
				if substrLen - maxFreq <= k:
					maxLen = max(maxLen, substrLen)
				else:
					break
	return maxLen

Optimal (Sliding Window)

Here the validation logic is same that for a substring st - len(st) - max(freq of st_i) <= k. But as the length of substring can be considered as a window (in context for sliding window technique) we can make the invalid window, valid by moving the left pointer l.

Key Insight:
We don’t decrease maxFreq when shrinking the window. Even if it’s outdated, it doesn’t affect correctness because:

• It only makes the window appear “more valid”.
• The actual window size (r - l + 1) ensures correctness.
• Avoids expensive recomputation.

def characterReplacement(self, s: str, k: int) -> int:
	maxLen = 0
	l = 0
	mp = {}
	maxFreq = 0
		for r in range(len(s)):
			mp[s[r]] = mp.get(s[r], 0) + 1
			maxFreq = max(maxFreq, mp[s[r]])
			substrLen = r - l + 1
			if substrLen - maxFreq <= k:
				maxLen = max(maxLen, substrLen)
			else:
				mp[s[l]] -= 1
				l += 1
	return maxLen