[C++ & Java] Explained - 2 different approach with 4 pass and 1 pass solution
Intuition
Observations :

the (N , S) pair and (E, W) pairs are independent and can be treated separately
We need to revert one from (N , S) pair and one from (
# Intuition
- Observations :
   - the (N , S) pair and (E, W) pairs are independent and can be treated separately
   - We need to revert one from (N , S) pair and one from (E, W) pairs at max k times combining both revert
   - We don't know which one to pick, so check all possible 4 cases

# Approach 1 ( 4 iteration )
- We need to covert first k occurance of (N, E) or (N, W) or (S, E) or (S, W) pairs to its opposite directions

- So chek all four cases and return the maximum

# Complexity
- Time complexity: O(N)

- Space complexity: (1)
- 
# Code
```cpp []
int maxDistance(string s, int k) {
    int ans = 0;
    char dir[4][2] = {{'N', 'E'}, {'N', 'W'},{'S', 'E'},{'S', 'W'}};
    for(auto d: dir) {
        for(int i = 0, curr = 0, t = k; i < s.size(); ++i){
            if(s[i] == d[0] || s[i] == d[1]){
                if(t > 0 ) { t--; curr++; }
                else curr--;
            }else curr++;
            ans = max(ans, curr); 
        }
    }
    return ans;
}
```
```java []
int maxDistance(String s, int k) {
    int ans = 0;
    char[][] dir = new char[][]{{'N', 'E'}, {'N', 'W'},{'S', 'E'},{'S', 'W'}};
    for(char[] d: dir) {
        for(int i = 0, curr = 0, t = k; i < s.length(); ++i){
            if(s.charAt(i) == d[0] || s.charAt(i) == d[1]){
                if(t > 0 ) { t--; curr++; }
                else curr--;
            }else curr++;
            ans = Math.max(ans, curr); 
        }
    }
    return ans;
}

```



# Approach 2 : ( 1 iteration ) 
Credit :  Thansk to [@pugaz2006](https://leetcode.com/u/pugaz2006/) for this approch.
Observation: 
- The intuition here is : we need to check the diff in opposite dir at any point should be the min distance for sure we can have. Then we try to revert one of the opposite dir to optimal dir and this way we can increase distance to diff + min(2*k, total item till now - diff). Here the diff is sum of diff in both direction. Basically, apart from the diff items, we can convert other opposite pairs one of the direction to get a larger dist. This can be possible untill we have 2*k ietems apart from the one that contribute to diff. A bit hard to graps this, but will become easy once you start doing some dry run with some test input.

Visualisation: 
Let say given string is NSNSSEWWW and k = 3
I am just doing it for one iteration ( say i = 7 ) you can try for other iterations on your own.

when i = 5 the string under consideration is NSNSSEWW
Here freq are N 2 times, S 3 times E 1 times W 2 times
NN
SSS
E
WW

the diff are 1 for NS and 1 for WE, total diff = 2
You can see from the count as well that the 2 N cancel 2S and 1 W cancel 1E effect and we just left out with 2 distance unit.

Now as we have a value k = 3 items we can change, ans we can have total items (i = 1 = 8)
=> there are nulifying pairs item count = 8 - diff = 8 - 2 = 6 items
As the 6 items are equal to 2*k, that means we can reverse direction of 3 items that will lead to addition of extra 6 items in the same direction and we will get total distance as 6 + 2 = 8



```cpp []
int maxDistance(string s, int k) {
    int ans = 0;
    unordered_map<char, int> freq;
    for(int i = 0; i < s.size(); ++i){
        freq[s[i]]++;
        int diff = abs(freq['N'] - freq['S']) + abs(freq['E'] - freq['W']);
        ans = max(ans, diff + min(2*k, i+1 - diff)); 
    }
    return ans;
}
```
```java []
int maxDistance(String s, int k) {
    int ans = 0;
    Map<Character, Integer> freq = new HashMap<>();
    for(int i = 0; i < s.length(); ++i){
        freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i),0) + 1);
        int diff = Math.abs(freq.getOrDefault('N',0) - freq.getOrDefault('S',0)) + Math.abs(freq.getOrDefault('E',0) - freq.getOrDefault('W',0));
        ans = Math.max(ans, diff + Math.min(2*k, i+1 - diff)); 
    }
    return ans;
}
```

---

<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:
https://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted

---
['C++', 'Java']