Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.
 
Example 1:
Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:
Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:
Input: text = "aaabbaaa"
Output: 4

Example 4:
Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:
Input: text = "abcdef"
Output: 1

 
Constraints:

1 <= text.length <= 20000
text consist of lowercase English characters only.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Amortized analysis

Starter code: class Solution:
    def maxRepOpt1(self, text: str) -> int:
        

Solutions:
class Solution:

	def maxRepOpt1(self, text: str) -> int:
		letters = {}
		for (i, char) in enumerate(text):
			if char in letters:
				letters[char].append(i)
			else:
				letters[char] = [i]
		if len(letters) == 1:
			return len(text)
		ans = 0
		for letter in letters:
			cur = 0
			prev = 0
			discarded = False
			maxSoFar = 0
			arr = letters[letter]
			for (j, pos) in enumerate(arr):
				if not j:
					cur = 1
				elif pos - arr[j - 1] == 1:
					cur += 1
				else:
					if not discarded and prev:
						discarded = True
					elif not discarded and pos - arr[j - 1] > 2:
						discarded = True
					if prev + cur > maxSoFar:
						maxSoFar = prev + cur
					if pos - arr[j - 1] == 2:
						prev = cur
						cur = 1
					else:
						prev = 0
						cur = 1
			print(prev + cur)
			if prev + cur > maxSoFar:
				maxSoFar = prev + cur
			if discarded:
				maxSoFar += 1
			if maxSoFar > ans:
				ans = maxSoFar
		return ans


class Solution:

	def maxRepOpt1(self, S: str) -> int:
		A = [[c, len(list(g))] for (c, g) in itertools.groupby(S)]
		count = collections.Counter(S)
		res = max((min(k + 1, count[c]) for (c, k) in A))
		for i in range(1, len(A) - 1):
			if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1:
				res = max(res, min(A[i - 1][1] + A[i + 1][1] + 1, count[A[i + 1][0]]))
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		for (k, g) in itertools.groupby(text):
			print(list(g))
		G = [[k, len(list(g))] for (k, g) in itertools.groupby(text)]
		c = collections.Counter(text)
		res = max((min(n + 1, c[k]) for (k, n) in G))
		for i in range(1, len(G) - 1):
			if G[i - 1][0] == G[i + 1][0] and G[i][1] == 1:
				res = max(min(G[i - 1][1] + G[i + 1][1] + 1, c[G[i - 1][0]]), res)
		return res


import itertools
import collections

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		import collections
		counter = collections.Counter(text)
		cnt = collections.defaultdict(int)
		start = res = max_cnt = 0
		for (end, char) in enumerate(text):
			cnt[char] += 1
			max_cnt = max(max_cnt, cnt[char])
			while end - start + 1 > max_cnt + 1:
				cnt[text[start]] -= 1
				max_cnt = max(cnt.values())
				start += 1
			res = max(res, min(end - start + 1, counter[char]))
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		be = 1
		n = collections.Counter(text)
		maxl = 0
		i = 1
		re = []
		now = text[0]
		while i < len(text):
			if now == text[i]:
				be += 1
			if now != text[i] or i == len(text) - 1:
				res = be
				if len(re) >= 2:
					print(re)
					(com, lencom) = re.pop(0)
					if re[-1][1] == 1 and com == now:
						res = lencom + be
				if res < n[now]:
					res += 1
				maxl = max(maxl, res)
				re.append((now, be))
				now = text[i]
				be = 1
			i += 1
		return maxl


import itertools
from collections import Counter

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		ref = [[letter, len(list(s))] for (letter, s) in itertools.groupby(text)]
		count = Counter(text)
		res = max([min(count.get(i), k + 1) for (i, k) in ref])
		for i in range(1, len(ref) - 1):
			if ref[i - 1][0] == ref[i + 1][0] and ref[i][1] == 1:
				res = max(res, min(ref[i - 1][1] + ref[i + 1][1] + 1, count.get(ref[i - 1][0])))
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		text_cnt = collections.Counter(text)
		d = collections.Counter()
		(l, r) = (0, 0)
		maxcnt = 0
		res = 0
		N = len(text)
		for (r, ch) in enumerate(text):
			d[ch] += 1
			maxcnt = max(maxcnt, d[ch])
			while r - l + 1 > maxcnt + 1:
				d[text[l]] -= 1
				maxcnt = max(d.values())
				l += 1
			res = max(res, min(r - l + 1, text_cnt[ch]))
		return res


from collections import Counter

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		if len(text) == 1:
			return 1
		counts = Counter(text)
		pre = [1]
		nex = [1]
		ans = 1
		for i in range(1, len(text)):
			if text[i] == text[i - 1]:
				pre.append(pre[-1] + 1)
			else:
				pre.append(1)
			ans = max(pre[i], ans)
		for i in range(len(text) - 2, -1, -1):
			if text[i] == text[i + 1]:
				nex.append(nex[-1] + 1)
			else:
				nex.append(1)
			ans = max(nex[len(text) - i - 1], ans)
		nex.reverse()
		for i in range(len(text)):
			if i != len(text) - 1 and text[i] != text[i + 1]:
				l = nex[i + 1]
				if counts[text[i + 1]] > l:
					ans = max(ans, 1 + l)
			if i != 0 and text[i] != text[i - 1]:
				l = pre[i - 1]
				if counts[text[i - 1]] > l:
					ans = max(ans, 1 + l)
			if i != 0 and i != len(text) - 1 and (text[i - 1] == text[i + 1]):
				l = pre[i - 1] + nex[i + 1]
				if counts[text[i - 1]] > l:
					ans = max(ans, 1 + l)
				else:
					ans = max(ans, l)
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		inuse = collections.defaultdict(int)
		left = collections.defaultdict(int)
		MOVE_TO_THE_NEXT_CHAR = 1
		REPLACE = 0
		LEAVE_AS_IT_IS = -1
		(res, i, n) = (1, 0, 0)
		for ch in text:
			left[ch] += 1
		for (j, ch) in enumerate(text):
			inuse[ch] += 1
			left[ch] -= 1
			n = max(inuse[ch], n)
			action = j - i - n
			char_exists = False
			if action >= MOVE_TO_THE_NEXT_CHAR:
				inuse[text[i]] -= 1
				left[text[i]] += 1
				i += 1
			elif action == REPLACE:
				char_exists = left[ch] > 0
			elif action == LEAVE_AS_IT_IS:
				char_exists = True
			if char_exists and j - i >= res:
				res = j - i + 1
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		from collections import Counter
		counter = Counter(text)
		if not text:
			return 0
		if len(text) == 1:
			return 1

		def helper(text):
			(start_idx, end_idx) = (0, 0)
			first_found = None
			ret = 0
			while end_idx < len(text):
				if text[end_idx] == text[start_idx]:
					end_idx += 1
					if counter[text[start_idx]] >= end_idx - start_idx:
						ret = max(ret, end_idx - start_idx)
					else:
						ret = max(ret, end_idx - start_idx - 1)
				elif not first_found:
					first_found = end_idx
					end_idx += 1
					if counter[text[start_idx]] >= end_idx - start_idx:
						ret = max(ret, end_idx - start_idx)
					else:
						ret = max(ret, end_idx - start_idx - 1)
				else:
					start_idx = end_idx = first_found
					first_found = None
			return ret
		return max(helper(text), helper(text[::-1]))


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		c = Counter(text)
		window = Counter()
		i = 0
		ans = 1
		for j in range(len(text)):
			c[text[j]] -= 1
			window[text[j]] += 1
			if len(window) == 1 or (len(window) == 2 and min(window.values()) == 1 and (c[sorted(window, key=window.get)[1]] > 0)):
				ans = max(ans, j - i + 1)
			else:
				c[text[i]] += 1
				window[text[i]] -= 1
				if window[text[i]] == 0:
					del window[text[i]]
				i += 1
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		n = len(text)
		win = collections.Counter()

		def valid_win(win):
			if len(win) > 2:
				return False
			if len(win) == 1:
				return True
			return not all((n >= 2 for n in win.values()))
		max_c_idx = {}
		min_c_idx = {}
		for (i, c) in enumerate(text):
			if c not in max_c_idx:
				max_c_idx[c] = i
			elif i > max_c_idx[c]:
				max_c_idx[c] = i
			if c not in min_c_idx:
				min_c_idx[c] = i
		(left, right) = (0, 0)
		ans = 0
		while right < n:
			c = text[right]
			right += 1
			win[c] += 1
			while not valid_win(win) and left < right:
				d = text[left]
				left += 1
				win[d] -= 1
				if win[d] == 0:
					win.pop(d)
			if len(win) == 1:
				ans = max(ans, right - left)
			else:
				(k1, k2) = win.keys()
				if win[k1] == 1 and (max_c_idx[k2] >= right or min_c_idx[k2] < left):
					ans = max(ans, right - left)
				elif win[k2] == 1 and (max_c_idx[k1] >= right or min_c_idx[k1] < left):
					ans = max(ans, right - left)
				else:
					ans = max(ans, right - left - 1)
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		max_char = ''
		clist = [1] * len(text)
		one_max = 1
		compress_list = []
		for i in range(1, len(text)):
			if text[i] == text[i - 1]:
				clist[i] = clist[i - 1] + 1
			else:
				clist[i] = 1
				compress_list.append([text[i - 1], clist[i - 1]])
			if clist[i] > one_max:
				one_max = clist[i]
				max_char = text[i]
		compress_list.append([text[-1], clist[-1]])
		print(compress_list)
		two_count = []
		two_max = 0
		for i in range(2, len(compress_list)):
			if compress_list[i - 1][1] > 1:
				continue
			if compress_list[i][0] != compress_list[i - 2][0]:
				continue
			if compress_list[i][1] + compress_list[i - 2][1] + 1 < two_max:
				continue
			c = compress_list[i][0]
			swaped = False
			for j in range(len(compress_list)):
				if j >= i - 2 and j <= i:
					continue
				if compress_list[j][0] == c:
					len2 = compress_list[i][1] + compress_list[i - 2][1] + 1
					two_count.append(len2)
					if len2 > two_max:
						two_max = len2
					swaped = True
			if swaped:
				continue
			len2 = compress_list[i][1] + compress_list[i - 2][1]
			two_count.append(len2)
			if len2 > two_max:
				two_max = len2
		if one_max >= two_max:
			char_count = 0
			for i in range(len(compress_list)):
				if compress_list[i][0] == max_char:
					char_count += 1
			if char_count > 1:
				one_max += 1
		return max(one_max, two_max)


from collections import Counter

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		if len(text) == 0:
			return 0
		seen = set()
		max_count = 0
		i = j = 0
		window = Counter()
		maxes = Counter()
		while j < len(text):
			if len(window) > 2 or (len(window) == 2 and min(window.values()) != 1):
				maxes[text[i]] = max(maxes[text[i]], window[text[i]])
				window[text[i]] -= 1
				if window[text[i]] == 0:
					del window[text[i]]
				i += 1
			else:
				inc = 0
				cur_char = text[j]
				window[cur_char] += 1
				if cur_char in maxes:
					max_count = max(max_count, maxes[cur_char] + 1)
					inc = 1
				max_count = max(max_count, window[cur_char] + inc)
				j += 1
		return max_count


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		n = len(text)
		ans = 1
		mp = {}
		for i in text:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		for i in mp:
			first = 0
			second = 0
			if i in mp:
				for j in range(0, n):
					if text[j] == i:
						first += 1
						if first + second < mp[i]:
							ans = max(ans, first + second + 1)
						else:
							ans = max(ans, first + second)
					else:
						if j != 0 and j != n - 1 and (text[j - 1] == i) and (text[j + 1] == i):
							second = first
						else:
							second = 0
						first = 0
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		if not text:
			return 0
		compact = [[text[0], 1]]
		max_ = 1
		for i in range(1, len(text)):
			if text[i] == compact[-1][0]:
				compact[-1][1] += 1
			else:
				compact.append([text[i], 1])
			max_ = max(max_, compact[-1][1])
		last_idx = defaultdict(int)
		for i in range(len(compact)):
			last_idx[compact[i][0]] += compact[i][1]
		for i in range(len(compact) - 2):
			if compact[i][0] == compact[i + 2][0] and compact[i + 1][1] == 1 and (compact[i][1] + compact[i + 2][1] < last_idx[compact[i][0]]):
				max_ = max(max_, compact[i][1] + compact[i + 2][1] + 1)
			if compact[i][0] == compact[i + 2][0] and compact[i + 1][1] == 1:
				max_ = max(max_, compact[i][1] + compact[i + 2][1])
		for i in range(len(compact)):
			if last_idx[compact[i][0]] > compact[i][1]:
				max_ = max(max_, compact[i][1] + 1)
		return max_


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		groups = []
		for (key, group) in itertools.groupby(text):
			groups.append([key, len(list(group))])
		count = collections.Counter(text)
		for index in range(len(groups)):
			if index <= len(groups) - 3:
				if groups[index + 1][1] == 1 and groups[index + 2][0] == groups[index][0]:
					groups[index][1] += groups[index + 2][1]
			if count[groups[index][0]] > groups[index][1]:
				groups[index][1] += 1
		maxlength = 0
		for group in groups:
			if group[1] > maxlength:
				maxlength = group[1]
		return maxlength


class Solution:

	def maxRepOpt1(self, text: str) -> int:

		def get_possible(idx, cur, step, swap):
			if idx >= len(positions):
				return step + swap
			if positions[idx] - 1 == cur:
				return get_possible(idx + 1, positions[idx], step + 1, swap)
			elif not swap:
				return step
			else:
				return max(step + 1, get_possible(idx, cur + 1, step + 1, False), get_possible(idx, positions[idx] - 1, 1, False), get_possible(idx + 1, positions[idx], 1, True))
		(letters, ans) = (defaultdict(list), 0)
		for (i, c) in enumerate(text):
			letters[c].append(i)
		for (_, positions) in letters.items():
			if len(positions) < 3:
				ans = max(ans, len(positions))
				continue
			x = min(get_possible(1, positions[0], 1, True), len(positions))
			ans = max(x, ans)
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		ln = len(text)
		if ln == 1:
			return 1
		mx = -1
		start = 0
		while start < ln:
			print(start, ',', end='')
			i = start + 1
			inx = -1
			while i < ln and (text[start] == text[i] or inx == -1):
				if text[start] != text[i]:
					inx = i
				i += 1
			print(i, ',', end='')
			if inx != -1 and (text[start] in text[i:] or text[start] in text[:start]):
				mx = max(mx, i - start)
			elif inx == -1 and (text[start] in text[i:] or text[start] in text[:start]):
				mx = max(mx, i - start + 1)
			elif inx == -1:
				mx = max(mx, i - start)
			else:
				mx = max(mx, i - start - 1)
			if inx == -1:
				start = i
			else:
				start = inx
			print(mx)
		return mx


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		tcounter = Counter(text)
		res = 0
		counter = Counter()
		i = 0
		for j in range(len(text)):
			counter[text[j]] += 1
			while j - i + 1 - max(counter.values()) > 1:
				counter[text[i]] -= 1
				i += 1
			curr_max = max(counter.values())
			c = [k for k in counter if counter[k] == curr_max][0]
			res = max(res, min(j - i + 1, tcounter[c]))
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		d = {}
		f = {}
		for i in text:
			d[i] = []
			f[i] = f.get(i, 0) + 1
		for i in list(d.keys()):
			s = 0
			same = 0
			diff = 0
			for j in text:
				if j == i:
					s = 1
				if j == i and s == 1:
					if diff:
						d[i].append(-diff)
					same += 1
					diff = 0
				else:
					if same:
						d[i].append(same)
					diff += 1
					same = 0
			if same:
				d[i].append(same)
			if diff:
				d[i].append(-diff)
		l = 0
		print(d)
		for i in list(d.keys()):
			for (j, v) in enumerate(d[i]):
				if v > 0:
					l = max(l, v)
					if j + 2 < len(d[i]) and d[i][j + 1] == -1:
						if d[i][j + 2] + d[i][j] < f[i]:
							l = max(l, d[i][j + 2] + d[i][j] + 1)
						else:
							l = max(l, d[i][j + 2] + d[i][j])
					elif d[i][j] < f[i]:
						l = max(l, d[i][j] + 1)
		return l


from collections import Counter

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		if not text:
			return 0
		cnt = Counter(list(text))
		print(cnt)
		output = 0
		for (c, n) in list(cnt.items()):
			val = 0
			holder = 0
			for (i, t) in enumerate(text):
				if t == c:
					val += 1
				else:
					holder = val
					val = 0
				if val + holder < n:
					op = val + holder + 1
				else:
					op = val + holder
				output = max(output, op)
		return output


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		count = Counter(text)
		i = 0
		diff = 1
		sol = 0
		while i < len(text):
			c = text[i]
			j = i + 1
			found = False
			while j < len(text):
				if text[j] == c:
					j += 1
				else:
					if found:
						if count[c] >= j - i:
							sol = max(sol, j - i)
						else:
							sol = max(sol, j - i - 1)
						break
					found = True
					diff = j
					j += 1
			if j == len(text):
				if count[c] > j - i and (not found):
					sol = max(sol, j - i + 1)
				if count[c] >= j - i:
					sol = max(sol, j - i)
				else:
					sol = max(sol, j - i - 1)
				break
			i = diff
		return sol


class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		r = x
		while not self.par[r] < 0:
			r = self.par[r]
		t = x
		while t != r:
			tmp = t
			t = self.par[t]
			self.par[tmp] = r
		return r

	def unite(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if rx == ry:
			return
		if self.rank[rx] <= self.rank[ry]:
			self.par[ry] += self.par[rx]
			self.par[rx] = ry
			if self.rank[rx] == self.rank[ry]:
				self.rank[ry] += 1
		else:
			self.par[rx] += self.par[ry]
			self.par[ry] = rx

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]

class Solution:

	def maxRepOpt1(self, text: str) -> int:
		n = len(text)
		cnt = Counter(list(text))
		uf = Unionfind(n)
		for i in range(n - 1):
			if text[i] == text[i + 1]:
				uf.unite(i, i + 1)
		ans = 0
		for i in range(n):
			ans = max(ans, uf.count(i) + (1 if uf.count(i) < cnt[text[i]] else 0))
		for i in range(n - 2):
			if text[i] == text[i + 2] and text[i] != text[i + 1]:
				total = uf.count(i) + uf.count(i + 2)
				ans = max(ans, total + (1 if total < cnt[text[i]] else 0))
		return ans


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		(lst, lookup) = (list(), dict())
		ptr = 0
		while ptr < len(text):
			(curr, count) = (text[ptr], 0)
			while ptr < len(text) and curr == text[ptr]:
				count += 1
				ptr += 1
			lookup[curr] = lookup.get(curr, 0) + count
			lst.append((curr, count))
		res = 0
		for i in range(len(lst)):
			if 0 < i < len(lst) - 1:
				if lst[i - 1][0] == lst[i + 1][0] and lst[i][1] == 1:
					curlen = lst[i - 1][1] + lst[i + 1][1]
					if lookup[lst[i - 1][0]] > curlen:
						curlen += 1
					res = max(res, curlen)
					continue
			curlen = lst[i][1]
			if lookup[lst[i][0]] > curlen:
				curlen += 1
			res = max(res, curlen)
		return res


class Solution:

	def maxRepOpt1(self, text: str) -> int:
		hashmap = {}
		wordlist = []
		(l, r, ans) = (0, 0, 0)
		while r < len(text):
			while r < len(text) and text[l] == text[r]:
				r += 1
			wordlist.append([text[l], r - l])
			if text[l] not in hashmap:
				hashmap[text[l]] = r - l
			else:
				hashmap[text[l]] += r - l
			l = r
		for (ch, count) in wordlist:
			ans = max(ans, min(count + 1, hashmap[ch]))
		for i in range(1, len(wordlist) - 1):
			if wordlist[i - 1][0] == wordlist[i + 1][0] and wordlist[i][1] == 1:
				ans = max(ans, min(wordlist[i - 1][1] + wordlist[i + 1][1] + 1, hashmap[wordlist[i + 1][0]]))
		return ans