Easy and Simple Greedy Solution O(N) single pass || O(1) Space
IntuitionApproachIterate through left to right in the string and keep count of N, S, E, W encountered till now, I have kept that count in variables
'posx' for N
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
Iterate through left to right in the string and keep count of N, S, E, W encountered till now, I have kept that count in variables 
* 'posx' for N
* 'negx' for S
* 'posy' for E
* 'negy' for S

After that, for each index, calculate minimums from both pairs (posx,negx) and (posy,negy), since we want to change the direction in the minority to get max distance from origin.
* Suppose we have 'posx' as 3 and 'negx' as 1 (distance (3-1)=2), we can observe that if we change posx, updated values become 'posx'=2 and 'negx'=2(distance(2-2)=0) but if we change the lower one, updated values become 'posx'=4 and 'negx'=0 (distance(4-0)=4). 
From this we can clearly determine that changing minimum values are always optimal.
* After this we can get count of how many values we can update, since there is limit k of how many we can change, that can be done by adding the two minimums from the pair and taking their minimum to k.
numberChanges=(sum of minimum of two pairs,k)
* Now finally, we have to calculate total distance, that can easily be done by observing that for each change we get an change of 2 in the total sum, so we first find the original distance without change then add 2*changes to it and compare it with current maximum!




# 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 posx=0,posy=0,negx=0,negy=0,ans=0;
        for(auto i:s){
            if(i=='N') posy++;
            if(i=='S') negy++;
            if(i=='E') posx++;
            if(i=='W') negx++;
            int need1=min(posx,negx),need2=min(posy,negy),val=min(k,need1+need2);
            ans=max(ans,max(posx,negx)-min(posx,negx)+max(posy,negy)-min(posy,negy)+2*val);
        }
        return ans;
        
    }
};
```
['Greedy', 'C++']