🔥Python3 FAST 🔥 - Simple Greedy Counting
Intuition

Since every move is along one of the coordinate axes, the Manhattan distance changes by exactly +1 (if the move is taken in a direction that takes yo
# Intuition
- Since every move is along one of the coordinate axes, the Manhattan distance changes by exactly `+1` (if the move is taken in a direction that takes you further from the origin) or `-1` (if the move brings you closer).
 
- When a move would decrease your Manhattan distance (a `-1` change), you can use one of your allowed modifications (`k`) to flip that move. Changing a move from one that subtracts `1` (i.e., `-1` change) to one that adds `1` gives a net gain of `+2` compared to the original move.

- It is always beneficial to flip a move that reduces the Manhattan distance, provided you still have modifications left. By doing this greedily as you simulate the path, you can ensure that you maximize the cumulative Manhattan distance reached at some point.

# Approach

1. **Initialize Variables:**
   - `x, y` for the current coordinates.
   - `cur, prev` to store the current and previous Manhattan distances.
   - `total` to accumulate the effective change in Manhattan distance as you simulate the path.
   - `best` to record the maximum Manhattan distance observed.

2. **Simulate the Path:**
   - Loop over each character `c` in the string `s`:
     - Update the current position `(x, y)` using the dictionary `dirs`.
     - Compute the current Manhattan distance `cur = abs(x) + abs(y)`.
     - Calculate the difference `diff = cur - prev` (this will be either `+1` or `-1`).
     - **Greedy Modification:**  
       If `diff` is `-1` (i.e., the move would reduce the Manhattan distance) **and** you have a modification available (`k > 0`), flip the move by setting `diff` to `+1` and decrement `k`.
     - Add `diff` to `total` and update `best` if `total` exceeds the current `best`.
     - Update `prev` to `cur` for the next iteration.
     
3. **Return the Maximum Distance:**
   - After processing all moves, return `best` as the maximum Manhattan distance reached.


# Complexity
- **Time Complexity:**  
  $$O(n)$$, where $$n$$ is the length of the string `s`, because we iterate through the string once.

- **Space Complexity:**  
  $$O(1)$$, as we use only a constant amount of extra space.


# Code
```python3 []
class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        dirs = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}

        x, y = 0, 0
        prev, cur = 0, 0
        total, best = 0, 0

        for c in s:
            x += dirs[c][0]
            y += dirs[c][1]
            cur = abs(x) + abs(y)
            diff = cur - prev
            prev = cur

            if diff == -1 and k > 0:
                diff = 1
                k -= 1
            total += diff
            if total > best:
                best = total

        return best
```

# Further Explanation

- **Simulation:**  
  The code simulates the movement based on the input string. For each move, it calculates how the Manhattan distance changes.

- **Greedy Modification:**  
  Whenever a move would have reduced the Manhattan distance (i.e., `diff == -1`), the code checks if it can "flip" that move (if `k > 0`) so that instead of decreasing the distance, it increases it by `1`. This flip effectively gives a net improvement of `2` compared to the original move.

- **Tracking Maximum Distance:**  
  By maintaining a running sum (`total`) of the effective changes and updating `best` along the way, the algorithm captures the maximum Manhattan distance reached at any point.

This greedy strategy ensures that you make the most out of your allowed modifications, resulting in the maximum possible Manhattan distance from the origin during the journey.

![Screenshot From 2025-02-02 10-27-36.png](https://assets.leetcode.com/users/images/2a380ab5-83b5-459f-b48c-bf4c9a8f6d58_1738521889.5337386.png)


['Greedy', 'Simulation', 'Counting', 'Python3']