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'.
Solution:
class Solution {
public int balancedString(String s) {
HashMap<Character,Integer> map = new HashMap<>();
int target = s.length()/4;
int minlen = s.length();
//save the occurence of characters in map
for(char c:s.toCharArray())
map.put(c,map.getOrDefault(c,0)+1);
//if the string is already balanced return 0
if(isBalanced(map,target)) return 0;
int left=0;
for (int right = 0; right < s.length(); right++)
{
map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
if (isBalanced(map, target))
{
minlen = Math.min(minlen, right - left + 1);
while(left<= right)
{
map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
left++;
if (isBalanced(map, target))
{
minlen = Math.min(minlen, right - left + 1);
}
else
break;
}
}
}
return minlen;
}
private boolean isBalanced(HashMap<Character,Integer> map,int target)
{
for (Map.Entry<Character,Integer> entry : map.entrySet())
{
if(entry.getValue()>target)
return false;
}
return true;
}
}