top of page
Search

# 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

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