[C++] Greedy + Count Moves on Opposite Axes, ~98% Time (33ms), ~100% Space (31.02MB)
In order to solve this problem, we just need to think about how the movements work, with instructions to move on the NS or on the WE axes cancelling each other
In order to solve this problem, we just need to think about how the movements work, with instructions to move on the `NS` or on the `WE` axes cancelling each other out.

With that in mind, we know that:
* the best move would be to take the largest value on each of the axes and nullify as many as possible of the opposite directions with our `k` transformations to turn them into more of the largest direction;
* it does not matter whether we spend our `k` transformation vertically or horizontally, as long as we manage to maximise the movements in those direction, since the resulting Manhattan distance would be the same;
* we will have to check at each step how we can spend our `k` transfomations optimally to maximise our score.

To do so, we will start declaring our support variables:
* `dirs` will store the maximum amount of steps on all the `4` directions, all initially set to be `0`;
* `origK` will store the original value of `k`;
* `minVal` and `maXVal` will store the minimum and maximum amount of steps we can do on each axis, respectively;
* `tmp` will store how much we can transform on each axis (being the minimum between the smaller value and how many transformations we have left to spend);
* `curr` will be our current best, at each step;
* `res` will store our absolute best, initially set to be `0`.

Time to parse our instractions! For each character `c` in `s`, we will:
* increase the matching value in `dirs` - and since I wanted to have some extra fun, I mapped the `4` possible characters so that we will use bitwise matching respectively for:
    * `1001110` for `'N`, matching `dirs[0]`;
    * `1010111` for `'W'`, matching `dirs[2]`;
    * `1010011` for `'S'`, matching `dirs[1]`;
    * `1000101` for `'E'`, matching `dirs[3]`;
* set `curr` to be `0`;
* set `k` to be `origK`;
* give `maxVal` the maximum value between `dirs[0]` and `dirs[1]`;
* give `minVal` the minimum value between `dirs[0]` and `dirs[1]`;
* give `tmp` the minimum value between `k` and `minVal`;
* decrease `k` by `tmp`;
* increase the current distance `curr` by `maxVal` plus `tmp`, minus the decreased value of `minVal`, again by `tmp` (which results in `maxVal - minVal + 2 * tmp`);
* give `maxVal` the maximum value between `dirs[2]` and `dirs[3]`;
* give `minVal` the minimum value between `dirs[2]` and `dirs[3]`;
* give `tmp` the minimum value between `k` and `minVal`;
* decrease `k` by `tmp`;
* increase the current distance `curr` by `maxVal` plus `tmp`, minus the decreased value of `minVal`, again by `tmp` (which results in `maxVal - minVal + 2 * tmp`);
* update `res` to be tha maximum value between its current one and `curr`.

Once done, we can just `return` `res` :)

# Complexity
- Time complexity: $$O(n)$$
- Space complexity: $$O(1)$$

# Code
```cpp
class Solution {
public:
    int maxDistance(string &s, int k) {
        // support variables
        int dirs[4] = {}, origK = k, minVal, maxVal, tmp, curr, res = 0;
        for (int c: s) {
            // North
            if (!(c & 1)) dirs[0]++;
            // West
            else if ((c & 7) == 7) dirs[2]++;
            // South
            else if ((c & 2) == 2) dirs[1]++;
            // East
            else dirs[3]++;
            // computing curr
            curr = 0, k = origK;
            // checking the NS axis
            if (dirs[0] > dirs[1]) maxVal = dirs[0], minVal = dirs[1];
            else maxVal = dirs[1], minVal = dirs[0];
            tmp = min(k, minVal);
            k -= tmp;
            curr += maxVal - minVal + (tmp << 1);
            // checking the WE axis
            if (dirs[2] > dirs[3]) maxVal = dirs[2], minVal = dirs[3];
            else maxVal = dirs[3], minVal = dirs[2];
            tmp = min(k, minVal);
            k -= tmp;
            curr += maxVal - minVal + (tmp << 1);
            // updating res
            res = max(res, curr);
        }
        return res;
    }
};
```
We can refactor a bit our logic inside the main loop to make our code DRYer while checking on the two axes.

# Complexity
- Time complexity: $$O(n)$$
- Space complexity: $$O(1)$$

# Code
```cpp
class Solution {
public:
    int maxDistance(string &s, int k) {
        // support variables
        int dirs[4] = {}, origK = k, minVal, maxVal, tmp, curr, res = 0;
        for (int c: s) {
            // North
            if (!(c & 1)) dirs[0]++;
            // West
            else if ((c & 7) == 7) dirs[2]++;
            // South
            else if ((c & 2) == 2) dirs[1]++;
            // East
            else dirs[3]++;
            // computing curr
            curr = 0, k = origK;
            // checking the NS and WE axes
            for (int i = 0, j = 1; k && i < 3; i += 2, j += 2) {
                if (dirs[i] > dirs[j]) maxVal = dirs[i], minVal = dirs[j];
                else maxVal = dirs[j], minVal = dirs[i];
                tmp = min(k, minVal);
                k -= tmp;
                curr += maxVal - minVal + (tmp << 1);
            }
            // updating res
            res = max(res, curr);
        }
        return res;
    }
};
```
# Brag
![image.png](https://assets.leetcode.com/users/images/ebe89747-68b9-4440-abdb-9a2267502f4f_1739058344.9607282.png)

['Math', 'String', 'Greedy', 'Counting', 'C++']