[leetcode]1234. Replace the Substring for Balanced String

문제

You are given a string s of length n containing only four 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 s balanced. If s is already balanced, return 0.

예시

• 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". 

제한사항

n == s.length
4 <= n <= 105
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.

풀이1

new Map()또는 {} Object를 통해 "Q","W","E", "R",의 개수를 세어 보려 했지만,
개수를 같게 맞춰야한다는 생각에 코드를 완성하거나 풀이해 내지 못했다.

풀이2

Sliding Windows방식을 사용한다.

• SlidingWindows Velog 포스팅

var balancedString = function (s) {
  let map = {
    Q: 0,
    W: 0,
    E: 0,
    R: 0,
  };

  for (let i = 0; i < s.length; i++) {
    map[s[i]]++;
  }

  console.log(map);

  let limit = Math.floor(s.length / 4);
console.log("limit", limit)
  let ans = Infinity;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
      console.log("i",i,start)
    map[s[i]]--;

    while (
      start <= s.length &&
      map['Q'] <= limit &&
      map['W'] <= limit &&
      map['E'] <= limit &&
      map['R'] <= limit
    ) {
      ans = Math.min(ans, i - start + 1);
      map[s[start]]++;
      start++;
    console.log("while",map)
    }
      console.log(map)
  }

  return ans;
};

목표는 "Q", "W", "E", "R"이 모두 limit 이하가 되게 하려면 최소 몇개를 빼면 되느냐이다.
따라서 SlidingWindows 알고리즘처럼 앞에서부터 하나의 원소씩 뺐을 때 만약 조건을 만족한다면 다시 앞부터 하나의 원소씩 넣어서 조건을 만족하는지 알아본다.
그부분의 while문의 부분이다.

그 외

같은 문자가 반복되는지 찾는것, 최대값을 찾는것과 같은 문제도 O(n)의 시간복잡도를 갖게 하려면 Sliding Windows로 풀이할 수 있다.