Formatted question description: https://leetcode.ca/all/1234.html

1234. Replace the Substring for Balanced String (Medium)

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
  • contains only 'Q', 'W', 'E' and 'R'.

Related Topics:
Two Pointers, String

Solution 1. Sliding Window

Count the frequency of each characters. Those characters with frequency greater than N / 4 must be replaced. Find the minimum window which covers those characters that should be replaced.

// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int balancedString(string s) {
        int N = s.size(), ans = N, i = 0, j = 0, replace = 0;
        unordered_map<char, int> m;
        for (char c : s) m[c]++;
        for (auto &[c, cnt] : m) {
            if ((m[c] = max(0, cnt - N / 4)) > 0) ++replace;
        }
        if (replace == 0) return 0;
        while (j < N) {
            replace -= --m[s[j++]] == 0;
            while (replace <= 0) {
                ans = min(ans, j - i);
                replace += m[s[i++]]++ == 0;
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/

// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window
class Solution {
public:
    int balancedString(string s) {
        unordered_map<char, int> m;
        int N = s.size(), ans = N, i = 0, k = N / 4;
        for (char c : s) ++m[c];
        for (int j = 0; j < N; ++j) {
            --m[s[j]];
            while (i < N && m['Q'] <= k && m['W'] <= k && m['E'] <= k && m['R'] <= k) {
                ans = min(ans, j - i + 1);
                ++m[s[i++]];
            }
        }
        return ans;
    }
};

Java

class Solution {
    public int balancedString(String s) {
        Map<Character, Integer> letterIndexMap = new HashMap<Character, Integer>();
        letterIndexMap.put('Q', 0);
        letterIndexMap.put('W', 1);
        letterIndexMap.put('E', 2);
        letterIndexMap.put('R', 3);
        int[] counts = new int[4];
        int length = s.length();
        int balanceLength = length / 4;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int index = letterIndexMap.get(c);
            counts[index]++;
        }
        boolean flag = true;
        for (int i = 0; i < 4; i++) {
            if (counts[i] > balanceLength) {
                counts[i] -= balanceLength;
                flag = false;
            } else
                counts[i] = 0;
        }
        if (flag)
            return 0;
        int[] actualCounts = new int[4];
        int minLength = length;
        int start = 0, end = 0;
        while (end < length) {
            char c = s.charAt(end);
            int index = letterIndexMap.get(c);
            if (counts[index] > 0) {
                actualCounts[index]++;
                if (canBalance(counts, actualCounts)) {
                    minLength = Math.min(minLength, end - start + 1);
                    while (start < end) {
                        char prevC = s.charAt(start);
                        start++;
                        int prevIndex = letterIndexMap.get(prevC);
                        if (counts[prevIndex] > 0) {
                            actualCounts[prevIndex]--;
                            if (actualCounts[prevIndex] < counts[prevIndex])
                                break;
                        }
                        minLength = Math.min(minLength, end - start + 1);
                    }
                }
            }
            end++;
        }
        return minLength;
    }

    public boolean canBalance(int[] counts, int[] actualCounts) {
        for (int i = 0; i < 4; i++) {
            if (actualCounts[i] < counts[i])
                return false;
        }
        return true;
    }
}

All Problems

All Solutions