1234. Replace the Substring for Balanced String (Java, Sliding Window, Leetcode)

 

 

class Solution {
    public int balancedString(String s) {
        //caching
        var cache = new int[128];
        int n = s.length(), result = n, k = n / 4;
        for (var ch : s.toCharArray()) {
            cache[ch]++;
        }
        //sliding windows
        var slow = 0; var fast = 0;
        while (fast < n) {
            //fast pointer goes while slow pointer condition does not meet.
            //decrease cache frequency.
            cache[s.charAt(fast)]--;
            fast++;
            
            //caused by fast pointer action(decreasing cache frequency).
            while (slow < n && cache['Q'] <= k && cache['W'] <= k && cache['E'] <= k && cache['R'] <= k) {
                //shortest window.
                result = Math.min(result, fast - slow);
                
                //revoke cache frequency.
                cache[s.charAt(slow)]++;
                slow++;
            }
        }
        return result;
    }
}

 

레퍼런스

https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window

[Java/C++/Python] Sliding Window - LeetCode Discuss