# Replace the Substring for Balanced String

Updated: Mar 25, 2021

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;
}
}
```