You are given a string containing only 4 kinds of characters 'Q', 'W', 'E' and 'R'.
A string is said to be balanced if each of its characters appears n/4 times where n is the length of the string.
Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string s balanced.
Return 0 if the string is already balanced.
 
Example 1:
Input: s = "QWER"
Output: 0
Explanation: s is already balanced.
Example 2:
Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:
Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER". 

Example 4:
Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

 
Constraints:

1 <= s.length <= 10^5
s.length is a multiple of 4
s contains only 'Q', 'W', 'E' and 'R'.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Amortized analysis

Starter code: class Solution:
    def balancedString(self, s: str) -> int:
        

Solutions:
class Solution:

	def balancedString(self, s: str) -> int:
		if len(s) // 4 != len(s) / 4:
			return -1
		(ans, lb, n_cnt) = (len(s), 0, collections.Counter(s))
		i = 0
		while i < len(s):
			n_cnt[s[i]] -= 1
			while lb < len(s) and all((len(s) / 4 >= n_cnt[c] for c in 'QWER')):
				ans = min(ans, abs(i - lb + 1))
				if ans == 0:
					return 0
				n_cnt[s[lb]] += 1
				lb += 1
			if lb > i:
				(i, lb) = (lb, i)
			i += 1
		return ans


class Solution:

	def balancedString(self, s: str) -> int:
		if len(s) // 4 != len(s) / 4:
			return -1
		(ans, p1, p2, n_cnt) = (len(s), 0, 0, collections.Counter(s))
		while p1 < len(s):
			n_cnt[s[p1]] -= 1
			while p2 < len(s) and all((len(s) / 4 >= n_cnt[c] for c in 'QWER')):
				ans = min(ans, abs(p1 - p2 + 1))
				n_cnt[s[p2]] += 1
				p2 += 1
			if p2 > p1:
				(p1, p2) = (p2, p1)
			p1 += 1
		return ans

	def balancedString(self, s: str) -> int:
		if len(s) // 4 != len(s) / 4:
			return -1
		(ans, p1, p2, n_cnt) = (len(s), 0, 0, collections.Counter(s))
		while p1 < len(s):
			n_cnt[s[p1]] -= 1
			while p2 < min(p1 + 2, len(s)) and all((len(s) / 4 >= n_cnt[c] for c in 'QWER')):
				ans = min(ans, abs(p1 - p2 + 1))
				n_cnt[s[p2]] += 1
				p2 += 1
			p1 += 1
		return ans


from sys import maxsize
from collections import Counter

class Solution:

	def balancedString(self, s):
		n = len(s)
		right = 0
		chars = Counter(s)
		res = maxsize
		for left in range(n):
			while right <= n - 1 and any((chars[c] > n // 4 for c in 'QWER')):
				chars[s[right]] -= 1
				right += 1
			if all((chars[c] <= n // 4 for c in 'QWER')):
				res = min(res, right - left)
			chars[s[left]] += 1
		return res