Simple min-max
IntuitionSince we're calculating Manhattan distance, the contribution of vertical or horizontal movement is equivalent. i.e. if we're north, and we receive an e
# Intuition
Since we're calculating Manhattan distance, the contribution of vertical or horizontal movement is equivalent. i.e. if we're north, and we receive an east/west direction, we don't need to flip it, it will still contribute the same to the Manhattan distance.

If we are currently north and encounter a south, it is important to flip the south to north (if possible) before we continue. Flipping to north when you are already north will add +1 to the distance. Flipping to E/W will also add +1 (but we'll need to go in the direction that we already are in; i.e. go east if we're east, or go west if we're already west). But taking the south will add -1 to the distance. So, two possibilities exist (+1 or -1). If you perform a switch, you go from -1 to +1 with a delta change of +2. You can skip the E/W analysis since that requires extra computation, you can just stick with north as we already have that number considered against south.

You can apply the same logic to all directions, since they are equivalent in Manhattan distance terms.

# Approach
Since the question asks about max distance from origin at any point, we need to consider all indices of the string.


We keep a running count of all the frequencies of directions we see so far in variables `n`, `s`, `w`, `e`.

At each index, after we have the current frequencies, we need to see if we are north or south and east or west. For example, if we are north, it means we have `n` > `s`. At this point, it would be best to flip all the `s`'s to `n`'s to go as far as possible. The limiting factor would be `k`. So we take the `min(s,k)` to flip. These will contribute +2 for each flip. Now, we would be `n-s + 2*min(s,k)` distance northward.

Since we've used up some flips in N/S, we only have some or no flips remaining. This is `k - min(s,k)` for the example above. We do the same thing for E/W.

You can simplify your code to not need to identify if you are north or south based on the `distY = abs(n-s) + min(n,s,k)`. Similarly, for east and west.

# Complexity
- Time complexity:
`O(N)` - only loop through the whole length of string once

- Space complexity:
`O(1)` - only storing freq and fixed number of calculations

# Code
```java []
class Solution {
    public int maxDistance(String str, int k) {
        char sc[] = str.toCharArray();
        int N = sc.length, dist = 0, max = 0, n = 0, s = 0, e = 0, w = 0;

        if (N == 1) return 1;

        for (int i = 0; i < N; ++i) {
            switch (sc[i]) {
                case 'N': n++;
                    break;
                case 'S': s++;
                    break;
                case 'W': w++;
                    break;
                case 'E': e++;
                    break;
            }

            int usedUpInNS = Math.min(k, Math.min(n,s));
            int distY = Math.abs(n-s) + 2*usedUpInNS;
            int distX = Math.abs(e-w) + 2*Math.min(k-usedUpInNS, Math.min(e,w));
            max = Math.max(max, distX + distY);
        }
        return max;
    }
}
```
['Java']