C++ ||  Greedy 
IntuitionTrying all possible pairs of chnages that we can make.Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
##### Trying all possible pairs of chnages that we can make.



# Code
```cpp []
class Solution {
public:
    // Calculate manhatten distance of a chnaged string
    int helper(string s) {
        int n = s.size();
        int x = 0, y = 0;
        int maxi = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == 'N')
                y++;
            else if (s[i] == 'S')
                y--;
            else if (s[i] == 'E')
                x++;
            else if (s[i] == 'W')
                x--;

            maxi = max(maxi, abs(x) + abs(y));
        }

        return maxi;
    }

    int maxDistance(string s, int k) {
        int n = s.size();
        int ans = 0;

        // SW - means we will change S and W in string i.e (S to N) and (W to E)
        // in similar fashion we will find strings after each pair of changes
        // that are possible Then we will take maximum from that
        string SW = "", SE = "";
        string NW = "", NE = "";
        int freq = k;

        for (int i = 0; i < n; i++) {
            if (s[i] == 'W' && k > 0) {
                SW += 'E';
                k--;
            } else if (s[i] == 'S' && k > 0) {
                SW += 'N';
                k--;
            } else {
                SW += s[i];
            }
        }

        k = freq;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'W' && k > 0) {
                NW += 'E';
                k--;
            } else if (s[i] == 'N' && k > 0) {
                NW += 'S';
                k--;
            } else {
                NW += s[i];
            }
        }

        k = freq;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'S' && k > 0) {
                SE += 'N';
                k--;
            } else if (s[i] == 'E' && k > 0) {
                SE += 'W';
                k--;
            } else {
                SE += s[i];
            }
        }

        k = freq;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'N' && k > 0) {
                NE += 'S';
                k--;
            } else if (s[i] == 'E' && k > 0) {
                NE += 'W';
                k--;
            } else {
                NE += s[i];
            }
        }

        return max({helper(NE), helper(NW), helper(SE), helper(SW)});
    }
};
```
['Greedy', 'C++']