Intuative brute force solution | easy to understand | beats 100% time (36ms)
Intuition & ApproachSee code commentsComplexity
Time complexity: O(n)
Space complexity: O(1)
Code
# Intuition & Approach

_See code comments_

# Complexity

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

# Code

```cpp []
int maxDistance(string s, int k) {
    int E = 0, W = 0, N = 0, S = 0, x = 0, y = 0, Md = 0;
    for (char ch : s) {
        if (ch == 'N')
            y++, N++;
        else if (ch == 'S')
            y--, S++;
        else if (ch == 'E')
            x++, E++;
        else
            x--, W++;

        // We will replace chars on x and y directions.
        // To maximise, will replace rx + ry, upto k can be replaced
        int rx = min(E, W), ry = min(N, S), j = min(k, rx + ry);
        // We get additional 2 * j when we do replacement
        Md = max(abs(x) + abs(y) + 2 * j, Md);
    }
    return Md;
}
```
['C++']