[leetcode 1234]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'.

풀이

- map 사용: map<char, int> m;
- 슬라이딩 윈도우 사용

- end 지점부터 문자열이 균형을 이루면 start를 이동한다.  

- result가 체크하는 것은 무슨 문자든 상관없이 균형을 파괴하는 문자들의 수를 세는 것

- 뽀인뜨: result = min(result, end-start+1) ; 불균형 문자열의 최대 길이 중 최솟값을 찾는 것이다.

ex) QQQWERRR이라고 해보자.

end가 5(첫 번째 R)이 되어야 end 뒤가 균형 문자열이 된다. 이 때 result = 5-0+1 =6

start가 2일때 start앞이 마지막 균형문자열이 된다. 이 때 result = 5-2+1 = 4

즉 QQQWERRR 가운데 볼드체가 바뀌어야 하는 최소 substring이라는 뜻이다. output = 4

 

class Solution {
public:
    int balancedString(string s) {
       map<char, int>m;
        
        for(int i=0; i<s.length(); i++){
            m[s[i]]++;
        }
        
        int start=0;
        int k = s.length()/4;
        int result = s.length();
        
        for(int end=0; end<s.length(); end++){
            m[s[end]]--;
            
            //조건을 만족할때만 start를 움직인다. 
            while(start<s.length() && m['W']<=k && m['E'] <=k
                  && m['Q']<=k && m['R']<=k){
                result = min(result, end-start+1);
                //result는 균형을 파괴하는 문자열 길이: [end, start]
                m[s[start]]++;
                start++;
            }
        }
        
        return result;
    }
};