1234. Replace the Substring for Balanced String LeetCode Solution
In this guide, you will get 1234. Replace the Substring for Balanced String LeetCode Solution with the best time and space complexity. The solution to Replace the Substring for Balanced String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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”.
Constraints:
n == s.length
4 <= n <= 105
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.
Complexity Analysis
Time Complexity:
Space Complexity:
1234. Replace the Substring for Balanced String LeetCode Solution in C++
class Solution {
public:
int balancedString(string s) {
const int n = s.length();
const int k = n / 4;
int ans = n;
vector<int> count(128);
for (const char c : s)
++count[c];
for (int i = 0, j = 0; i < n; ++i) {
--count[s[i]];
while (j < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k &&
count['R'] <= k) {
ans = min(ans, i - j + 1);
++count[s[j]];
++j;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1234. Replace the Substring for Balanced String LeetCode Solution in Java
class Solution {
public int balancedString(String s) {
final int n = s.length();
final int k = n / 4;
int ans = n;
int[] count = new int[128];
for (final char c : s.toCharArray())
++count[c];
for (int i = 0, j = 0; i < n; ++i) {
--count[s.charAt(i)];
while (j < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
ans = Math.min(ans, i - j + 1);
++count[s.charAt(j)];
++j;
}
}
return ans;
}
} // code provided by PROGIEZ
1234. Replace the Substring for Balanced String LeetCode Solution in Python
class Solution:
def balancedString(self, s: str) -> int:
ans = len(s)
count = collections.Counter(s)
j = 0
for i, c in enumerate(s):
count[c] -= 1
while j < len(s) and all(count[c] <= len(s) // 4 for c in 'QWER'):
ans = min(ans, i - j + 1)
count[s[j]] += 1
j += 1
return ans # code by PROGIEZ
