Given a string S and an integer K. In one operation, you are allowed to choose any character of the string and change it to any other uppercase English character.You can perform this operation atmost K times.
Return the length of the longest substring containing same letter you can get after performing the above operations.
Note : S consists of only uppercase English letters.
Example 1:
Input : 
S = "ABBA"
K = 2
Output: 4
Explanation: Replace the 2 occurrences of 'A' with 2 'B's or vice-versa.
Example 2:
Input :
S = "AABAABB"
k = 2
Output: 6
Explanation: Replace the occurrence of 'B' with 'A' and form "AAAAAAB".
The substring "AAAAAA" has the most extended repeating letters, which is 6.
 
Your task :
You don't have to read input or print anything. Your task is to complete the function characterReplacement() which takes the string S and integer K as input and returns the longest substring containing same letter after performing specified operations.
 
Expected Time Complexity : (|S|)
Expected Auxiliary Space : O(1)
 
Constraints :
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def characterReplacement(self, S, K):

        # Code here

Solutions:
class Solution:

	def characterReplacement(self, S, k):
		i = 0
		j = 0
		char_dict = {}
		longest_substring = 0
		while j < len(S):
			char_dict[S[j]] = char_dict.get(S[j], 0) + 1
			while max(char_dict.values()) + k < j - i + 1:
				char_dict[S[i]] -= 1
				i += 1
			longest_substring = max(longest_substring, j - i + 1)
			j += 1
		return longest_substring


class Solution:

	def characterReplacement(self, S, K):
		d = {}
		res = l = 0
		for r in range(len(S)):
			d[S[r]] = d.get(S[r], 0) + 1
			if r - l + 1 - max(d.values()) > K:
				d[S[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		(window_start, max_len, max_repeate_letter_count, hash_map) = (0, 0, 0, {})
		for window_end in range(len(S)):
			hash_map[S[window_end]] = 1 + hash_map.get(S[window_end], 0)
			max_repeate_letter_count = max(max_repeate_letter_count, hash_map[S[window_end]])
			if window_end - window_start + 1 - max_repeate_letter_count > K:
				hash_map[S[window_start]] -= 1
				window_start += 1
			max_len = max(max_len, window_end - window_start + 1)
		return max_len


class Solution:

	def characterReplacement(self, S, K):
		count = {}
		res = 0
		l = 0
		maxi = 0
		for r in range(len(S)):
			count[S[r]] = 1 + count.get(S[r], 0)
			maxi = max(maxi, count[S[r]])
			while r - l + 1 - maxi > K:
				count[S[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		freq = [0] * 26
		start = end = max_freq = result = 0
		for end in range(len(S)):
			freq[ord(S[end]) - ord('A')] += 1
			max_freq = max(max_freq, freq[ord(S[end]) - ord('A')])
			if end - start + 1 - max_freq > K:
				freq[ord(S[start]) - ord('A')] -= 1
				start += 1
			result = max(result, end - start + 1)
		return result


class Solution:

	def characterReplacement(self, s, k):
		map = {}
		res = 0
		l = 0
		maxf = 0
		for r in range(len(s)):
			map[s[r]] = 1 + map.get(s[r], 0)
			maxf = max(maxf, map[s[r]])
			while r - l + 1 - maxf > k:
				map[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		(l, r) = (0, 0)
		maxf = 0
		res = 0
		hashmap = {}
		while r < n:
			hashmap[s[r]] = 1 + hashmap.get(s[r], 0)
			maxf = max(maxf, hashmap[s[r]])
			if r - l + 1 - maxf > k:
				hashmap[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
			r += 1
		return res


class Solution:

	def characterReplacement(self, s, k):
		mp = [0 for i in range(26)]
		(maxi, fp, lp) = (0, 0, 0)
		ans = 0
		while lp < len(s) and fp <= lp:
			ind = ord(s[lp]) - 65
			mp[ind] += 1
			maxi = max(maxi, mp[ind])
			cost = lp - fp + 1 - maxi
			if cost <= k:
				ans = max(ans, lp - fp + 1)
			else:
				while fp <= lp:
					mp[ord(s[fp]) - 65] -= 1
					fp += 1
					maxi = max(maxi, mp[ind])
					if lp - fp + 1 - maxi <= k:
						ans = max(ans, lp - fp + 1)
						break
			lp += 1
		return ans


from collections import defaultdict

class Solution:

	def characterReplacement(self, S, K):
		left = 0
		n = len(S)
		hmap = defaultdict(int)
		maxi = 0
		for right in range(0, n):
			if S[right] not in hmap:
				hmap[S[right]] = 1
			else:
				hmap[S[right]] += 1
			while right - left + 1 - max(hmap.values()) > K:
				hmap[S[left]] -= 1
				if hmap[S[left]] == 0:
					del hmap[S[left]]
				left += 1
			maxi = max(maxi, right - left + 1)
		return maxi


class Solution:

	def characterReplacement(self, S, K):
		d = {}
		ans = 1
		(r, l) = (0, 0)
		while r < len(S):
			i = S[r]
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			while max(d.values()) + K < r - l + 1:
				d[S[l]] -= 1
				l += 1
			ans = max(ans, r - l + 1)
			r += 1
		return ans


class Solution:

	def characterReplacement(self, S, K):
		d = {}
		(maxf, answer, i) = (0, -1, 0)
		for j in range(len(S)):
			if S[j] in d:
				d[S[j]] += 1
			else:
				d[S[j]] = 1
			maxf = max(maxf, d[S[j]])
			while i < len(S) and j - i + 1 - maxf > K:
				d[S[i]] -= 1
				i += 1
			answer = max(answer, j - i + 1)
		return answer


class Solution:

	def characterReplacement(self, S, K):
		i = 0
		mp = {}
		maxoc = float('-inf')
		ans = 0
		for j in range(len(S)):
			if S[j] not in mp:
				mp[S[j]] = 0
			mp[S[j]] += 1
			maxoc = max(maxoc, mp[S[j]])
			if j - i + 1 - maxoc > K:
				mp[S[i]] -= 1
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def characterReplacement(self, S, K):
		i = 0
		j = 0
		count = dict()
		res = 0
		while j < len(S):
			count[S[j]] = 1 + count.get(S[j], 0)
			while j - i + 1 - max(count.values()) > K:
				count[S[i]] -= 1
				i += 1
			res = max(res, j - i + 1)
			j += 1
		return res


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		dic = defaultdict(int)
		ans = 0
		j = 0
		max_f = 0
		for i in range(len(s)):
			dic[s[i]] += 1
			max_f = max(max_f, dic[s[i]])
			while i - j + 1 - max_f > k:
				dic[s[j]] -= 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


class Solution:

	def characterReplacement(self, s, K):
		n = len(s)
		char_count = [0 for _ in range(26)]
		start = 0
		res = 0
		max_count = 0
		for end in range(n):
			char_count[ord(s[end]) - ord('A')] += 1
			current_char_count = char_count[ord(s[end]) - ord('A')]
			max_count = max(max_count, current_char_count)
			while end - start - max_count + 1 > K:
				char_count[ord(s[start]) - ord('A')] -= 1
				start += 1
			res = max(res, end - start + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		start = 0
		fre_map = {}
		max_fre = 0
		ans = 0
		for end in range(len(s)):
			fre_map[s[end]] = fre_map.get(s[end], 0) + 1
			max_fre = max(max_fre, fre_map[s[end]])
			is_valid = end + 1 - start - max_fre <= k
			if not is_valid:
				fre_map[s[start]] -= 1
				start += 1
			ans = end + 1 - start
		return ans


class Solution:

	def characterReplacement(self, S, K):
		l = 0
		r = 0
		maxFreq = 0
		n = len(S)
		ans = 0
		dic = dict()
		for r in range(n):
			if S[r] not in dic:
				dic[S[r]] = 0
			dic[S[r]] += 1
			maxFreq = max(maxFreq, dic[S[r]])
			while r - l + 1 - maxFreq > K:
				dic[S[l]] -= 1
				l += 1
			ans = max(ans, r - l + 1)
		return ans


import collections

class Solution:

	def characterReplacement(self, s, k):
		count = collections.defaultdict(int)
		l = 0
		res = 0
		for r in range(len(s)):
			count[s[r]] += 1
			while r - l + 1 - max(count.values()) > k:
				count[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		a = []
		for i in range(26):
			a.append(0)
		maxi = 0
		left = 0
		right = 0
		curlen = 0
		while right < len(S):
			curlen += 1
			a[ord(S[right]) - 65] += 1
			if curlen - max(a) <= K:
				if curlen > maxi:
					maxi = curlen
				right += 1
			else:
				while curlen - max(a) > K:
					curlen -= 1
					a[ord(S[left]) - 65] -= 1
					left += 1
				right += 1
		return maxi


class Solution:

	def characterReplacement(self, s, k):
		ans = 0
		ind = 0
		d = {}
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 0
			d[s[i]] += 1
			while i + 1 - ind - max(d.values()) > k:
				char = s[ind]
				d[char] -= 1
				ind += 1
			ans = max(ans, i - ind + 1)
		return ans


class Solution:

	def characterReplacement(self, S, K):
		s = S
		k = K
		d = {}
		i = 0
		res = 0
		maxe = 0
		for j in range(0, len(s)):
			d[s[j]] = d.get(s[j], 0) + 1
			maxe = max(d[s[j]], maxe)
			while j - i + 1 - maxe > k:
				d[s[i]] = d[s[i]] - 1
				i = i + 1
			res = max(j - i + 1, res)
		return res


class Solution:

	def characterReplacement(self, S, K):
		l = 0
		r = 0
		di = {}
		c = 0
		while r < len(S):
			if S[r] not in di:
				di[S[r]] = 1
			else:
				di[S[r]] += 1
			if r - l + 1 - max(di.values()) > K:
				di[S[l]] -= 1
				l += 1
			c = max(c, r - l + 1)
			r += 1
		return c


class Solution:

	def characterReplacement(self, S, K):
		(i, j) = (0, 0)
		ans = 0
		k = {}
		while i < len(S):
			if S[i] not in k:
				k[S[i]] = 1
			else:
				k[S[i]] += 1
			if i - j + 1 - max(k.values()) > K:
				k[S[j]] -= 1
				j += 1
			ans = max(ans, i - j + 1)
			i += 1
		return ans


class Solution:

	def characterReplacement(self, S, K):
		count = {}
		res = 0
		l = 0
		maxf = 0
		for i in range(len(S)):
			count[S[i]] = 1 + count.get(S[i], 0)
			maxf = max(maxf, count[S[i]])
			while i - l + 1 - maxf > K:
				count[S[l]] -= 1
				l += 1
			res = max(res, i - l + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		dct = {}
		l = 0
		res = 0
		for r in range(len(s)):
			dct[s[r]] = 1 + dct.get(s[r], 0)
			if r - l + 1 - max(dct.values()) > k:
				dct[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		i = 0
		j = 0
		maxi = 0
		d = {}
		while j < len(S):
			if S[j] in d:
				d[S[j]] += 1
			else:
				d[S[j]] = 1
			maxfreq = j - i + 1 - max(d.values())
			if maxfreq <= K:
				maxi = max(maxi, j - i + 1)
			if maxfreq > K:
				d[S[i]] -= 1
				i = i + 1
			j = j + 1
		return maxi


class Solution:

	def characterReplacement(self, S, K):
		d = {}
		res = 0
		i = 0
		n = len(S)
		for j in range(n):
			d[S[j]] = 1 + d.get(S[j], 0)
			while j - i + 1 - max(d.values()) > K:
				d[S[i]] -= 1
				i += 1
			res = max(j - i + 1, res)
		return res


from collections import defaultdict

class Solution:

	def characterReplacement(self, S, K):
		c = defaultdict(lambda : 0)
		n = len(S)
		i = 0
		j = 0
		maxi = 0
		while i < n - maxi:
			while j < n:
				c[S[j]] += 1
				if j - i == K + max(c.values()):
					c[S[j]] -= 1
					break
				j += 1
				maxi = max(maxi, j - i)
			c[S[i]] -= 1
			i += 1
		return maxi


class Solution:

	def characterReplacement(self, S, K):
		ctr = {}
		l = 0
		max_len = 0
		freq_max_char = 0
		for r in range(len(S)):
			ctr[S[r]] = 1 + ctr.get(S[r], 0)
			freq_max_char = max(freq_max_char, ctr[S[r]])
			while l <= r and r - l + 1 - freq_max_char > K:
				ctr[S[l]] -= 1
				l += 1
			max_len = max(max_len, r - l + 1)
		return max_len


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		ctr = defaultdict(lambda : 0)
		l = 0
		ans = 0
		max_repeat_chars = 0
		for r in range(len(s)):
			ctr[s[r]] += 1
			max_repeat_chars = max(max_repeat_chars, ctr[s[r]])
			while r - l + 1 - max_repeat_chars > k:
				ctr[s[l]] -= 1
				l += 1
			ans = max(ans, r - l + 1)
		return ans


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		visited = defaultdict(lambda : 0)
		res = 0
		l = 0
		freq = 0
		for r in range(len(s)):
			visited[s[r]] += 1
			freq = max(freq, visited[s[r]])
			while r - l + 1 - freq > k:
				visited[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		visited = {}
		res = 0
		l = 0
		freq = 0
		for r in range(len(s)):
			visited[s[r]] = 1 + visited.get(s[r], 0)
			freq = max(freq, visited[s[r]])
			while r - l + 1 - freq > k:
				visited[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		max_freq = 0
		count = {}
		res = 0
		n = len(s)
		l = 0
		for r in range(n):
			if s[r] in count:
				count[s[r]] += 1
			else:
				count[s[r]] = 1
			max_freq = max(max_freq, count[s[r]])
			if r - l + 1 - max_freq > k:
				count[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		dic = {}
		res = 0
		l = 0
		for r in range(len(S)):
			if S[r] in dic:
				dic[S[r]] += 1
			else:
				dic[S[r]] = 1
			while r - l + 1 - max(dic.values()) > K:
				dic[S[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, S, K):
		n = len(S)
		left = right = 0
		freq = {}
		ans = 1
		while right < n:
			ch = S[right]
			if ch in freq:
				freq[ch] += 1
			else:
				freq[ch] = 1
			while max(freq.values()) + K < right - left + 1:
				freq[S[left]] -= 1
				left += 1
			ans = max(ans, right - left + 1)
			right += 1
		return ans


from collections import Counter

class Solution:

	def characterReplacement(self, S, K):
		n = len(S)
		left = right = 0
		freq = Counter()
		ans = 1
		while right < n:
			ch = S[right]
			freq[ch] += 1
			while max(freq.values()) + K < right - left + 1:
				freq[S[left]] -= 1
				left += 1
			ans = max(ans, right - left + 1)
			right += 1
		return ans


class Solution:

	def characterReplacement(self, S, K):
		count = [0 for i in range(26)]
		maxchar = 0
		j = 0
		i = 0
		ans = 0
		while j < len(S):
			currchar = S[j]
			count[ord(currchar) - 65] += 1
			wsize = j - i + 1
			maxchar = max(maxchar, count[ord(currchar) - 65])
			rep = wsize - maxchar
			if rep > K:
				count[ord(S[i]) - 65] -= 1
				i = i + 1
			else:
				ans = max(ans, j - i + 1)
			j = j + 1
		return ans


import sys

class Solution:

	def characterReplacement(self, s, k):
		windowStart = 0
		maxLength = 0
		maxCount = 0
		d = {}
		for windowEnd in range(len(s)):
			rightChar = s[windowEnd]
			if rightChar not in d:
				d[rightChar] = 0
			d[rightChar] += 1
			maxCount = max(maxCount, d[rightChar])
			if windowEnd + 1 - windowStart - maxCount > k:
				leftChar = s[windowStart]
				d[leftChar] -= 1
				windowStart += 1
			maxLength = max(maxLength, windowEnd + 1 - windowStart)
		return maxLength


class Solution:

	def characterReplacement(self, S, K):
		low = 0
		high = 0
		ans = 0
		count = 0
		map = {}
		while high < len(S):
			if S[high] in map:
				map[S[high]] += 1
			else:
				map[S[high]] = 1
			count = max(count, map[S[high]])
			if high - low + 1 - count > K:
				map[S[low]] -= 1
				low += 1
			ans = max(ans, high - low + 1)
			high += 1
		return ans


class Solution:

	def characterReplacement(self, S, K):
		(l, h) = (0, 0)
		d = {}
		maxsize = 0
		while h < len(S):
			if S[h] not in d:
				d[S[h]] = 1
			else:
				d[S[h]] += 1
			maxf = max(list(d.values()))
			capacity = h - l + 1 - maxf
			while l <= h and capacity > K:
				d[S[l]] -= 1
				maxf = max(list(d.values()))
				l += 1
				capacity = h - l + 1 - maxf
			maxsize = max(maxsize, h - l + 1)
			h += 1
		return maxsize


class Solution:

	def characterReplacement(self, arr, K):
		start = end = answer = 0
		max_count = 0
		char_count = [0] * 26
		while end < len(arr):
			temp = ord(arr[end]) - ord('A')
			char_count[temp] += 1
			max_count = max(max_count, char_count[temp])
			while end - start - max_count + 1 > K:
				char_count[ord(arr[start]) - ord('A')] += -1
				start += 1
			answer = max(answer, end - start + 1)
			end += 1
		return answer


class Solution:

	def characterReplacement(self, S, K):
		s = S
		k = K
		count = {}
		res = 0
		maxf = 0
		l = 0
		for r in range(len(s)):
			count[s[r]] = 1 + count.get(s[r], 0)
			maxf = max(maxf, count[s[r]])
			while r - l + 1 - maxf > k:
				count[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


from collections import defaultdict

class Solution:

	def characterReplacement(self, S, K):
		start = 0
		dic = defaultdict(lambda : 0)
		res = 0
		maf = 0
		for i in range(len(S)):
			dic[S[i]] += 1
			maf = max(maf, dic[S[i]])
			while i - start + 1 - maf > K:
				dic[S[start]] -= 1
				start += 1
			res = max(res, i - start + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		length = max_l = l = 0
		dic = {s[0]: 1}
		for r in range(1, n):
			if s[r] in dic:
				dic[s[r]] += 1
			else:
				dic[s[r]] = 1
			maxx = 0
			for key in dic:
				if dic[key] >= maxx:
					maxx = dic[key]
			while r - l + 1 - maxx > k:
				dic[s[l]] += -1
				l += 1
				maxx = 0
				for key in dic:
					if dic[key] >= maxx:
						maxx = dic[key]
			if r - l + 1 - maxx <= k:
				max_l = max(r - l + 1, max_l)
		return max_l


class Solution:

	def characterReplacement(self, s, K):
		n = len(s)
		(l, r) = (0, 0)
		(length, max_l) = (1, 1)
		hm = {}
		hm[s[0]] = 1
		for i in range(1, n):
			if s[i] not in hm:
				hm[s[i]] = 1
			else:
				hm[s[i]] += 1
			r += 1
			maxx = 0
			for _ in hm:
				if hm[_] >= maxx:
					maxx = hm[_]
			length = r - l + 1
			rem = length - maxx
			if rem <= K:
				pass
			else:
				hm[s[l]] += -1
				l += 1
			length = r - l + 1
			max_l = max(max_l, length)
		return max_l


class Solution:

	def characterReplacement(self, S, K):
		(count, res) = ({}, 0)
		(l, r) = (0, 0)
		while r < len(S):
			count[S[r]] = 1 + count.get(S[r], 0)
			while r - l + 1 - max(count.values()) > K:
				count[S[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
			r += 1
		return res


class Solution:

	def characterReplacement(self, s, k):
		d = {}
		maxi = 0
		l = 0
		res = 0
		for r in range(len(s)):
			if s[r] not in d:
				d[s[r]] = 1
			else:
				d[s[r]] += 1
			maxi = max(maxi, d[s[r]])
			while r - l + 1 - maxi > k:
				d[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def characterReplacement(self, s, k):
		hm = {}
		ans = 0
		l = 0
		for r in range(len(s)):
			hm[s[r]] = 1 + hm.get(s[r], 0)
			while r - l + 1 - max(hm.values()) > k:
				hm[s[l]] -= 1
				l += 1
			ans = max(ans, r - l + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		count = {}
		res = 0
		l = 0
		maxfr = 0
		for r in range(len(s)):
			count[s[r]] = 1 + count.get(s[r], 0)
			maxfr = max(maxfr, count[s[r]])
			while r - l + 1 - maxfr > k:
				count[s[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


from collections import defaultdict

class Solution:

	def characterReplacement(self, S, K):
		dicti = defaultdict(int)
		left = 0
		maxCount = 0
		result = 0
		for right in range(len(S)):
			dicti[S[right]] += 1
			maxCount = max(maxCount, dicti[S[right]])
			while right - left + 1 - maxCount > K:
				dicti[S[left]] -= 1
				left += 1
			result = max(result, right - left + 1)
		return result


class Solution:

	def characterReplacement(self, S, K):
		count = {}
		f = 0
		res = 0
		for r in range(len(S)):
			count[S[r]] = 1 + count.get(S[r], 0)
			if r - f + 1 - max(count.values()) > K:
				count[S[f]] -= 1
				f += 1
			res = max(res, r - f + 1)
		return res


from collections import Counter

class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		left = right = mx = 0
		freq = Counter()
		ans = 1
		while right < n:
			ch = s[right]
			freq[ch] += 1
			while max(freq.values()) + k < right - left + 1:
				freq[s[left]] -= 1
				left += 1
			ans = max(ans, right - left + 1)
			right += 1
		return ans