1234-replace-the-substring-for-balanced-string.py

"""
Problem Link: https://leetcode.com/problems/replace-the-substring-for-balanced-string/

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'.
"""
class Solution:
    def balancedString(self, s: str) -> int:
      d = {'Q':0,'W':0,'E':0,'R':0}
      for c in s:
        d[c] += 1
      
      minLength = len(s)
      l = len(s) // 4
      i = 0
      start = 0
      while i < len(s):
        d[s[i]] -= 1
        while start < len(s) and d['Q'] <= l and d['W'] <= l and d['E'] <= l and d['R'] <= l:
          minLength = min(minLength,i-start+1)
          d[s[start]] += 1
          start += 1
        i += 1
      return minLength