Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1234.html
1234. Replace the Substring for Balanced String (Medium)
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^5s.lengthis a multiple of4scontains only'Q','W','E'and'R'.
Related Topics:
Two Pointers, String
Solution 1. Sliding Window
Count the frequency of each characters. Those characters with frequency greater than N / 4 must be replaced. Find the minimum window which covers those characters that should be replaced.
// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int balancedString(string s) {
int N = s.size(), ans = N, i = 0, j = 0, replace = 0;
unordered_map<char, int> m;
for (char c : s) m[c]++;
for (auto &[c, cnt] : m) {
if ((m[c] = max(0, cnt - N / 4)) > 0) ++replace;
}
if (replace == 0) return 0;
while (j < N) {
replace -= --m[s[j++]] == 0;
while (replace <= 0) {
ans = min(ans, j - i);
replace += m[s[i++]]++ == 0;
}
}
return ans;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window
class Solution {
public:
int balancedString(string s) {
unordered_map<char, int> m;
int N = s.size(), ans = N, i = 0, k = N / 4;
for (char c : s) ++m[c];
for (int j = 0; j < N; ++j) {
--m[s[j]];
while (i < N && m['Q'] <= k && m['W'] <= k && m['E'] <= k && m['R'] <= k) {
ans = min(ans, j - i + 1);
++m[s[i++]];
}
}
return ans;
}
};
-
class Solution { public int balancedString(String s) { Map<Character, Integer> letterIndexMap = new HashMap<Character, Integer>(); letterIndexMap.put('Q', 0); letterIndexMap.put('W', 1); letterIndexMap.put('E', 2); letterIndexMap.put('R', 3); int[] counts = new int[4]; int length = s.length(); int balanceLength = length / 4; for (int i = 0; i < length; i++) { char c = s.charAt(i); int index = letterIndexMap.get(c); counts[index]++; } boolean flag = true; for (int i = 0; i < 4; i++) { if (counts[i] > balanceLength) { counts[i] -= balanceLength; flag = false; } else counts[i] = 0; } if (flag) return 0; int[] actualCounts = new int[4]; int minLength = length; int start = 0, end = 0; while (end < length) { char c = s.charAt(end); int index = letterIndexMap.get(c); if (counts[index] > 0) { actualCounts[index]++; if (canBalance(counts, actualCounts)) { minLength = Math.min(minLength, end - start + 1); while (start < end) { char prevC = s.charAt(start); start++; int prevIndex = letterIndexMap.get(prevC); if (counts[prevIndex] > 0) { actualCounts[prevIndex]--; if (actualCounts[prevIndex] < counts[prevIndex]) break; } minLength = Math.min(minLength, end - start + 1); } } } end++; } return minLength; } public boolean canBalance(int[] counts, int[] actualCounts) { for (int i = 0; i < 4; i++) { if (actualCounts[i] < counts[i]) return false; } return true; } } ############ class Solution { public int balancedString(String s) { int[] cnt = new int[4]; String t = "QWER"; int n = s.length(); for (int i = 0; i < n; ++i) { cnt[t.indexOf(s.charAt(i))]++; } int m = n / 4; if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) { return 0; } int ans = n; for (int i = 0, j = 0; i < n; ++i) { cnt[t.indexOf(s.charAt(i))]--; while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) { ans = Math.min(ans, i - j + 1); cnt[t.indexOf(s.charAt(j++))]++; } } return ans; } } -
// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/ // Time: O(N) // Space: O(1) class Solution { public: int balancedString(string s) { int N = s.size(), ans = N, i = 0, j = 0, replace = 0; unordered_map<char, int> m; for (char c : s) m[c]++; for (auto &[c, cnt] : m) { if ((m[c] = max(0, cnt - N / 4)) > 0) ++replace; } if (replace == 0) return 0; while (j < N) { replace -= --m[s[j++]] == 0; while (replace <= 0) { ans = min(ans, j - i); replace += m[s[i++]]++ == 0; } } return ans; } }; -
class Solution: def balancedString(self, s: str) -> int: cnt = Counter(s) n = len(s) if all(v <= n // 4 for v in cnt.values()): return 0 ans, j = n, 0 for i, c in enumerate(s): cnt[c] -= 1 while j <= i and all(v <= n // 4 for v in cnt.values()): ans = min(ans, i - j + 1) cnt[s[j]] += 1 j += 1 return ans ############ # 1234. Replace the Substring for Balanced String # https://leetcode.com/problems/replace-the-substring-for-balanced-string/ class Solution: def balancedString(self, s: str): n = len(s) desired = n // 4 c = Counter(s) for key in c: if c[key] > 0: c[key] = max(0, c[key] - desired) res = n i = 0 for j,x in enumerate(s): c[x] -= 1 while i < n and all(val <= 0 for val in c.values()): res = min(res, j - i + 1) c[s[i]] += 1 i += 1 return res def balancedString(self, s: str): n = len(s) c = Counter(s) res = float('inf') i = 0 for j,x in enumerate(s): c[x] -= 1 while i < n and all(val <= n//4 for val in c.values()): res = min(res, j - i + 1) c[s[i]] += 1 i += 1 return res -
func balancedString(s string) int { cnt := [4]int{} t := "QWER" n := len(s) for i := range s { cnt[strings.IndexByte(t, s[i])]++ } m := n / 4 if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m { return 0 } ans := n for i, j := 0, 0; i < n; i++ { cnt[strings.IndexByte(t, s[i])]-- for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m { ans = min(ans, i-j+1) cnt[strings.IndexByte(t, s[j])]++ j++ } } return ans } func min(a, b int) int { if a < b { return a } return b }