We have a string s of length n, which contains only UPPERCASE characters and we have a number k (always less than n). We can make at most k changes in our string. In one change, you can replace any s[i] (0<= i < n) with any uppercase character (from 'A' to 'Z'). After k changes, find the maximum possible length of the sub-string which have all same characters.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Change 2 'B' into 'A'. 
Now s = "AAAA"
Example:
Input: s = "ADBD", k = 1
Output: 3
Explanation: Change 'B' into 'D'.
Now s = "ADDD"
Your Task:
You don't need to read or print anything. Your task is to complete the function characterReplacement() which takes s and k as input parameters and returns the maximum length of sub-string after doing k changes.
 
Expected Time Complexity: O(n)
Expected Space Complexity: O(26)
 
Constraints:
1 <= n <= 10^{5}
0 <= k < n

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

	def characterReplacement(self, s, k):

		# Code here

Solutions:
class Solution:

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


import math

class Solution:

	def characterReplacement(self, s, k):
		windowStart = 0
		windowSize = -math.inf
		hashMap = {}
		maxCharacterCount = 0
		for windowEnd in range(len(s)):
			if s[windowEnd] not in hashMap:
				hashMap[s[windowEnd]] = 0
			hashMap[s[windowEnd]] += 1
			maxCharacterCount = max(maxCharacterCount, hashMap[s[windowEnd]])
			if windowEnd - windowStart + 1 - maxCharacterCount > k:
				hashMap[s[windowStart]] -= 1
				if hashMap[s[windowStart]] == 0:
					del hashMap[s[windowStart]]
				windowStart += 1
			windowSize = max(windowSize, windowEnd - windowStart + 1)
		return windowSize


class Solution:

	def characterReplacement(self, s, k):
		max_len = 0
		window_start = 0
		max_count = 0
		counts = [0] * 26
		for window_end in range(len(s)):
			char_index = ord(s[window_end]) - ord('A')
			counts[char_index] += 1
			max_count = max(max_count, counts[char_index])
			if window_end - window_start + 1 - max_count > k:
				counts[ord(s[window_start]) - ord('A')] -= 1
				window_start += 1
			max_len = max(max_len, window_end - window_start + 1)
		return max_len


class Solution:

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


import collections

class Solution:

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


class Solution:

	def characterReplacement(self, s, k):
		l = 0
		count = dict()
		res = 0
		maxf = 0
		for r in range(len(s)):
			count[s[r]] = count.get(s[r], 0) + 1
			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


class Solution:

	def characterReplacement(self, s, k):
		m = 0
		d = dict()
		ans = 0
		j = 0
		for i in range(len(s)):
			d[s[i]] = d.get(s[i], 0) + 1
			m = max(m, d[s[i]])
			if i - j + 1 - m > k:
				d[s[j]] = d.get(s[j], 0) - 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		freq = defaultdict(int)
		(res, max_len) = (0, 0)
		for (idx, val) in enumerate(s):
			freq[val] += 1
			max_len = max(max_len, freq[val])
			if res - max_len >= k:
				freq[s[idx - res]] -= 1
			else:
				res += 1
		return res


from collections import defaultdict

class Solution:

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


class Solution:

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


class Solution:

	def characterReplacement(self, s, k):
		h = [0] * 26
		maxi = float('-inf')
		i = 0
		j = 0
		mf = 0
		while j < len(s):
			h[ord(s[j]) - 65] += 1
			mf = max(mf, h[ord(s[j]) - 65])
			if j - i + 1 - mf > k:
				h[ord(s[i]) - 65] -= 1
				i += 1
			maxi = max(j - i + 1, maxi)
			j += 1
		return maxi


class Solution:

	def characterReplacement(self, s, k):
		has = {}
		maxi = 0
		let = ''
		left = 0
		right = 0
		res = 0
		while right < len(s):
			if s[right] not in has:
				has[s[right]] = 1
			else:
				has[s[right]] += 1
			maxi = max(maxi, has[s[right]])
			if right - left + 1 - maxi > k:
				has[s[left]] -= 1
				left += 1
			else:
				res = max(res, right - left + 1)
			right += 1
		return res


class Solution:

	def characterReplacement(self, s, k):
		max_freq = 0
		m = {}
		ans = 0
		j = 0
		for i in range(len(s)):
			if s[i] not in m:
				m[s[i]] = 1
			else:
				m[s[i]] += 1
			max_freq = max(max_freq, m[s[i]])
			if i - j + 1 - max_freq > k:
				m[s[j]] -= 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


from collections import defaultdict

class Solution:

	def characterReplacement(self, A, k):
		c = defaultdict(int)
		(res, maxcount) = (0, 0)
		for (idx, val) in enumerate(s):
			c[val] += 1
			maxcount = max(maxcount, c[val])
			if res - maxcount >= k:
				c[s[idx - res]] -= 1
			else:
				res += 1
		return res


class Solution:

	def characterReplacement(self, s, k):
		(mo, max_occr, ans, j) = ({}, 0, k + 1, 0)
		for i in range(len(s)):
			if s[i] not in mo:
				mo[s[i]] = 1
			else:
				mo[s[i]] += 1
			max_occr = max(max_occr, mo[s[i]])
			if i - j + 1 - max_occr > k:
				mo[s[j]] -= 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		f = [0] * 26
		start = 0
		maxCount = 0
		maxLength = 0
		for end in range(n):
			f[ord(s[end]) - ord('A')] += 1
			maxCount = max(maxCount, f[ord(s[end]) - ord('A')])
			while end - start + 1 - maxCount > k:
				f[ord(s[start]) - ord('A')] -= 1
				start += 1
			maxLength = max(maxLength, end - start + 1)
		return maxLength


class Solution:

	def characterReplacement(self, s, k):
		rep = 0
		maxi = 0
		start = -1
		dic = dict()
		i = 0
		while i < len(s):
			if s[i] in dic:
				dic[s[i]] += 1
			else:
				dic[s[i]] = 1
			maxi = max(maxi, dic[s[i]])
			l = i - start
			if l - maxi <= k:
				rep = max(rep, l)
			else:
				start += 1
				dic[s[start]] -= 1
			i += 1
		return rep


class Solution:

	def characterReplacement(self, s, k):
		mf = 0
		m = {}
		(a, j) = (0, 0)
		for i in range(len(s)):
			if s[i] not in m:
				m[s[i]] = 1
			else:
				m[s[i]] += 1
			mf = max(mf, m[s[i]])
			if i - j + 1 - mf > k:
				m[s[j]] -= 1
				j += 1
			a = max(a, i - j + 1)
		return a


class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		d = [0] * 26
		p = 0
		maxi = 0
		ans = 0
		for i in range(n):
			d[ord(s[i]) - ord('A')] += 1
			h = i + 1 - p
			maxi = max(maxi, d[ord(s[i]) - ord('A')])
			h1 = h - maxi
			if h1 <= k:
				ans = max(ans, h)
			else:
				d[ord(s[p]) - ord('A')] -= 1
				p += 1
		return ans


class Solution:

	def characterReplacement(self, s, k):
		(l, r) = (0, 0)
		(cur_max, ans) = (0, 1)
		d = [0] * 26
		for r in range(len(s)):
			d[ord(s[r]) - ord('A')] += 1
			cur_max = max(cur_max, d[ord(s[r]) - ord('A')])
			while r - l + 1 - cur_max > k:
				d[ord(s[l]) - ord('A')] -= 1
				l += 1
			ans = max(ans, r - l + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		(l, r) = (0, 0)
		(cur_max, ans) = (0, 1)
		d = [0] * 26
		while r < len(s):
			d[ord(s[r]) - ord('A')] += 1
			cur_max = max(cur_max, d[ord(s[r]) - ord('A')])
			if r - l + 1 - cur_max <= k:
				if r - l + 1 > ans:
					ans = r - l + 1
			else:
				d[ord(s[l]) - ord('A')] -= 1
				l += 1
			r += 1
		return ans


class Solution:

	def characterReplacement(self, s, k):
		d = {}
		i = 0
		j = 0
		maxlength = 0
		maxfreq = 0
		while j < len(s):
			if s[j] in d:
				d[s[j]] += 1
			else:
				d[s[j]] = 1
			maxfreq = max(maxfreq, d[s[j]])
			if j - i + 1 - maxfreq > k:
				if d[s[i]] > 1:
					d[s[i]] -= 1
				else:
					d.pop(s[i])
				i += 1
			maxlength = max(maxlength, j - i + 1)
			j += 1
		return maxlength


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		d = defaultdict(int)
		(i, j) = (0, 0)
		maxlen = 0
		ans = 0
		n = len(s)
		while j < n:
			ch = s[j]
			d[ch] += 1
			leng = j - i + 1
			maxlen = max(maxlen, d[ch])
			while j - i + 1 - maxlen > k:
				d[s[i]] -= 1
				i += 1
			ans = max(ans, j - i + 1)
			j += 1
		return ans


class Solution:

	def characterReplacement(self, s, k):
		ans = 0
		hs = dict()
		i = 0
		m = 0
		mx = 0
		for j in range(len(s)):
			if s[j] in hs:
				hs[s[j]] += 1
			else:
				hs[s[j]] = 1
			mx = max(mx, hs[s[j]])
			if j - i + 1 - mx > k:
				hs[s[i]] -= 1
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		mem = {chr(i): 0 for i in range(65, 91)}
		start = 0
		max_count = 0
		ans = 0
		for end in range(n):
			mem[s[end]] += 1
			max_count = max(max_count, mem[s[end]])
			while end - start + 1 - max_count > k:
				mem[s[start]] -= 1
				start += 1
			ans = max(ans, end - start + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		freq = {}
		start = 0
		maxFreq = 0
		length = 0
		for i in range(len(s)):
			if s[i] in freq:
				freq[s[i]] += 1
			else:
				freq[s[i]] = 1
			maxFreq = max(maxFreq, freq[s[i]])
			if i - start + 1 - maxFreq - k > 0:
				freq[s[start]] += -1
				start += 1
			else:
				length += 1
		return length


class Solution:

	def characterReplacement(self, s, k):
		d = {}
		max1 = 0
		max2 = 0
		j = 0
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] = d[s[i]] + 1
			max1 = max(max1, d[s[i]])
			if i + 1 - j - max1 <= k:
				max2 = max(max2, i + 1 - j)
			else:
				d[s[j]] = d[s[j]] - 1
				j = j + 1
		return max2


class Solution:

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


from collections import defaultdict

class Solution:

	def characterReplacement(self, s, k):
		d = defaultdict(int)
		(ans, maxcount) = (0, 0)
		for (idx, val) in enumerate(s):
			d[val] += 1
			maxcount = max(maxcount, d[val])
			if ans - maxcount >= k:
				d[s[idx - ans]] -= 1
			else:
				ans += 1
		return ans


from collections import Counter

class Solution:

	def characterReplacement(self, s, k):
		n = len(s)
		ans = 0
		larcount = 0
		i = 0
		char = {}
		for j in range(n):
			if s[j] in char:
				char[s[j]] += 1
			else:
				char[s[j]] = 1
			larcount = max(larcount, char[s[j]])
			if larcount + k < j - i + 1:
				char[s[i]] -= 1
				i += 1
			else:
				ans = max(ans, j - i + 1)
		return ans


class Solution:

	def characterReplacement(self, s, k):
		map = {}
		j = 0
		ans = 0
		maxx = 0
		for i in range(len(s)):
			if s[i] not in map:
				map[s[i]] = 1
			else:
				map[s[i]] += 1
			maxx = max(maxx, map[s[i]])
			if i - j + 1 - maxx > k:
				map[s[j]] -= 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


import collections

class Solution:

	def characterReplacement(self, s, k):
		maxf = 0
		res = 0
		count = collections.Counter()
		for i in range(len(s)):
			count[s[i]] += 1
			maxf = max(maxf, count[s[i]])
			if res - maxf < k:
				res += 1
			else:
				count[s[i - res]] -= 1
		return res


from collections import Counter

class Solution:

	def characterReplacement(self, s, k):
		(maxlen, largestCount) = (0, 0)
		arr = Counter()
		for idx in range(len(s)):
			arr[s[idx]] += 1
			largestCount = max(largestCount, arr[s[idx]])
			if maxlen - largestCount >= k:
				arr[s[idx - maxlen]] -= 1
			else:
				maxlen += 1
		return maxlen


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