Problem statement

https://binarysearch.com/problems/Balance-the-Directions/

Solution

The idea is to use two pointers/sliding window approach here. We are interested only in elements in sliding window with frequency >= n//4, so we look only at those subarrays, for which we have inside all extra letters. Then we can use problem Leetcod 0076. Minimum Window Substring.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        beg, end = 0, 0
        ans, found = float("inf"), 0
        cnt_t, cnt_s = Counter(s), Counter()
        for x in "NEWS":
            cnt_t[x] = max(0, cnt_t[x] - n//4)
            if cnt_t[x] == 0: cnt_t.pop(x)

        if not cnt_t: return 0
        while end <= len(s):
            if found == len(cnt_t):
                ans = min(ans, end - beg)
                old = s[beg]
                if cnt_s[old] == cnt_t[old]: found -= 1
                cnt_s[old] -= 1
                beg += 1
            else:
                if end == len(s): break
                new = s[end]
                if cnt_s[new] == cnt_t[new] - 1: found += 1
                cnt_s[new] += 1
                end += 1
        
        return ans