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".


  • 1 <= s.length <= 10^5

  • s.length is a multiple of 4

  • s contains only 'Q', 'W', 'E' and 'R'.


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())
        //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);  
                    if (isBalanced(map, target))
                        minlen = Math.min(minlen, right - left + 1);
       return minlen;
    private boolean isBalanced(HashMap<Character,Integer> map,int target)
        for (Map.Entry<Character,Integer> entry : map.entrySet())  
                return false;
        return true;

154 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.