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

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.