1351. Replace The Substring For Balanced String¶

LeetCode Problem View on GitHub

1351. Replace the Substring for Balanced String

Medium

You are given a string s of length n containing only four 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 s balanced. If s is already balanced, return 0.

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

Constraints:

• n == s.length
• 4 <= n <= 105
• n is a multiple of 4.
• s contains only 'Q', 'W', 'E', and 'R'.

Solution¶

class Solution {
    public int balancedString(String s) {
        int[] count = new int[128];
        char[] arr = s.toCharArray();
        for (char c: arr) count[c]++;
        int need = arr.length / 4;
        int left = 0, right = 0, min = arr.length;
        while (right <= arr.length) {
            if (count['Q'] > need || count['W'] > need || count['E'] > need || count['R'] > need) {
                if (right >= arr.length) break;
                char rightCh = arr[right];
                count[rightCh]--;
                right++;
                continue;
            }
            min = Math.min(min, right-left);
            if (min == 0) break;
            char leftCh = arr[left];
            count[leftCh]++;
            left++;
        }
        return min;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here