Minimize opposing directions
IntuitionWe need to minimize the opposing directions.
Opposing directions pairs being (N and S), (W and E).
We traverse the directions one by one, storing the f
# Intuition
We need to minimize the opposing directions.
Opposing directions pairs being (N and S), (W and E).
We traverse the directions one by one, storing the frequency
of direction instructions upto that point and find the optimal
result.

# Approach

When there are no opposing directions in the input (e.g., NNNE, NEN, SWWS), the max Manhattan distance is simply the length of the input: 4, 3 and 4 respectively. We see each direction increases the distance by 1, so we track this in a variable `dirs_sum`, which equals the number of directions processed so far.

Let's try adding one opposing direction to inputs now, (e.g., NNNE**W**, NEN**S**, SWWS**N**), each opposing pair (like N and S, or W and E) reduces the Manhattan distance by 2 because the directions cancel each other out. Therefore, the Manhattan distance after processing the last direction can be calculated with the following formula:

`man_dis = dirs_sum - 2 * (num_of_opposite_dirs)`

For each opposing pair (N vs S, W vs E), the number of opposites is the smaller count between the two directions. So, the total number of opposing pairs is the sum of the minimum values for each pair:
`num_of_opposite_dirs = min(freq["N"], freq["S"]) + min(freq["W"], freq["E"])`

Finally, to simulate the change of up to k directions, we undo the effect of the upto k opposing directions through addition.
`man_dis += (2 * min(k, num_of_opposite_dirs))`

We do this process for each direction in the input, updating `ans` whenever we find a greater distance.

# Complexity
- Time complexity:
$$O(n)$$


- Space complexity:
$$O(1)$$

# Code
```python3 []
class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        freq = defaultdict(int)
        ans = 0
        dirs_sum = 0 
        for c in s:
            freq[c] += 1
            dirs_sum += 1 # dirs_sum = sum(freq.values())
            num_of_opposite_dirs = min(freq["N"], freq["S"]) + min(freq["W"], freq["E"])
            # Current manhattan distance can be calculated by subtracting the
            # 2 * num_of_opposite_dirs from the sum of all directions.
            # Such direction will cancel the effect of itself
            # and opposing direction, thus twice the reduction.
            man_dis = dirs_sum - (2 * num_of_opposite_dirs) 
            # Simulate changing upto min(k, num_of_opposite_dirs) directions.
            # Such move will undo the effect done by the opposing direction.
            man_dis += (2 * min(k, num_of_opposite_dirs))
            ans = max(ans, man_dis)
        return ans

```
['Python3']