Diagonals
We can achieve the maximum Manhattan distance if our moves are either "NE", "NW", "SE" or "SW".So, for each diagonal direction, we explore the path while flippi
We can achieve the maximum Manhattan distance if our moves are either "NE", "NW", "SE" or "SW".

So, for each diagonal direction, we explore the path while flipping opposite moves up to `k` times.

> For example, if our direction is "NW", we flip "S" and "E" moves.

Alternatively, as suggested by [Aditya Agrawal](https://leetcode.com/u/adityaaagrawal489/), we can do this in one pass by "extending" the current directions by up to `2 * k`.

See the C++ solution for the detail.

# Code
```python3 []
class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        res = 0
        for diag in [{"N", "E"}, {"N", "W"}, {"S", "E"}, {"S", "W"}]:
            kk, dist = k, 0
            for ch in s:
                if ch in diag or kk:
                    dist += 1
                    kk -= ch not in diag
                else:
                    dist -= 1
                res = max(res, dist)
        return res
```
```cpp []
int maxDistance(string s, int k) {
    int res = 1, hor = 0, ver = 0;
    for (int i = 0; i < s.size(); ++i) {
        ver += s[i] == 'N' ? 1 : s[i] == 'S' ? -1 : 0;
        hor += s[i] == 'W' ? 1 : s[i] == 'E' ? -1 : 0;
        res = max(res, min(abs(hor) + abs(ver) + 2 * k, i + 1));
    }
    return res;
}
```
['Python3']