Exploring All Possible Directions | Greedy
IntuitionThe logic behind this question is pretty intuitive.
We have to move the point as far from the origin as possible.
Now there are two basic moves possibl
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The logic behind this question is pretty intuitive.
We have to move the point as far from the origin as possible.
Now there are two basic moves possible: 
    
- Either we move it in just one direction, ie, completely towards East/West/North/South.
- Or we move it in EN/ES/WN/WS.

So if we think optimally as the the string may/may not have all the four directions, it is always optimal to choose the second move in order to make it as far as possible from the origin as the first order would automatically be followed if we chose the second route/order.

So we simply apply this logic.

# Approach
<!-- Describe your approach to solving the problem. -->
So, we first try to move it in East-North (EN) direction by changing the first k `W` to `E` && `S` to `N` (Why first k? Beaucse we have to move in the order given and in such a case, in order to maximize the distance it is best to change the first k directions those not in favour). Then we simply calculate the max distance it will cover if we followed this route by calling the `dist` function in which, we simply take `E` as +x, `W` as -x, `N` as +y and `S` as -y and we store the max dist at any time from the origin.

Similarly we do for the directions:
`NW` , `WS` , `SE` (calculating the 4 quadrants in order).


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

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

# Code
```cpp []
class Solution {
public:

    int dist(string& s){
        int x = 0, y = 0;
        int ans = 0;
        for(char c: s){
            if(c=='E')x++;
            if(c=='W')x--;
            if(c=='N')y++;
            if(c=='S') y--;
            ans = max(ans, abs(x)+abs(y));
        }
        return ans;
    }

    int maxDistance(string s, int k) {
        string temp = s;
        int x = k, ans=0;

        // EN
        for(char &c: temp){     // using '&c' as the 'for-each' loop creates a copy and won't change the char when required.
            if(x>0 && c=='W') c='E',x--;
            if(x>0 && c=='S') c= 'N',x--;
        }
        ans= max(ans, dist(temp));

        // NW
        temp=s; x=k;
        for(char &c: temp){
            if(x>0 && c=='S') c='N',x--;
            if(x>0 && c=='E') c='W',x--;
        }
        ans= max(ans, dist(temp));

        // WS
        temp=s; x=k;
        for(char &c: temp){
            if(x>0 && c=='E') c='W',x--;
            if(x>0 && c=='N') c='S',x--;
        }
        ans= max(ans, dist(temp));

        // SE
        temp=s; x=k;
        for(char &c: temp){
            if(x>0 && c=='N') c='S',x--;
            if(x>0 && c=='W') c= 'E',x--;
        }
        ans= max(ans, dist(temp));

        return ans;
    }
};
```
['String', 'Greedy', 'Counting', 'C++']