Go in diagonals
IntuitionWe need to maximimize the distance from origin, so go in NE, NW, SE, SWApproachTry out all directions {NE, NW, SE, SW}
For each iterations try to go in
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need to maximimize the distance from origin, so go in NE, NW, SE, SW

# Approach
<!-- Describe your approach to solving the problem. -->
Try out all directions {NE, NW, SE, SW}
For each iterations try to go in that direction only

For example: Going NE (0, 0) -> (1, 0) -> (1, -1) -> (1, -2) ...

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(1)

# Code
```cpp []
class Solution {
public:
    int maxDistance(string s, int k) {
        int maxDis = 0;

        vector<vector<char>> diagonals = {
            {'N', 'E'}, 
            {'N', 'W'}, 
            {'S', 'E'}, 
            {'S', 'W'}
        };

        // Try going in all of the four directions
        for (auto diag : diagonals) {
            int tempK = k;
            int dist = 0;

            for (char ch : s) {
                if (ch == diag[0] || ch == diag[1]) {
                    dist++;
                } else if (tempK > 0) {
                    dist++;
                    tempK--;
                } else {
                    dist--;
                }

                maxDis = max(maxDis, dist);
            }
        }
        
        return maxDis;
    }
};
```
['C++']