🔥 100% Beat 🔥 | O(n) TC | O(1) SC | ✔️ Efficient Move Calculation ✔️ Optimal Solution
Intuition:The Manhattan distance is the sum of the absolute differences in the x and y coordinates. For this problem, the directions in the string move us along
![image.png](https://assets.leetcode.com/users/images/90cb3dd4-ba0f-46ff-8546-112cb3989ceb_1738481530.284058.png)


# Intuition:  
The Manhattan distance is the sum of the absolute differences in the x and y coordinates. For this problem, the directions in the string move us along these coordinates. By making changes (up to `k`), we can attempt to optimize the distance, which may involve swapping opposite directions (like changing 'S' to 'N', or 'E' to 'W').
---
# **Approach**

1. **Track Movement in Each Direction**:
   - Maintain four counters: one each for north (`northMoves`), south (`southMoves`), east (`eastMoves`), and west (`westMoves`).
   
2. **Track the Opposite Movements**:
   - The opposite directions cancel each other. For example, every north move that is followed by a south move reduces the overall displacement in the north-south direction. Similarly, east-west movements cancel out.
   
3. **Optimize the Movements**:
   - By changing up to `k` moves, we can adjust the number of cancellations. For example, if we have more south moves than north, we can change some of the south moves into north to increase the total north-south movement.
   
4. **Calculate Maximum Manhattan Distance**:
   - After processing each move in the string, calculate the Manhattan distance and keep track of the maximum distance achieved.
   
5. **Result**:
   - The result will be the maximum Manhattan distance observed during the entire sequence of movements.

---

### **Example**

#### **Example 1:**

**Input**:  
`s = "NWSE"`, `k = 1`

- Start at `(0, 0)` (origin).
- After each movement, track the coordinates and compute the Manhattan distance.

**Steps**:
1. **Move 1**: `N` → `(0, 1)`  
   - Manhattan Distance = `|0 - 0| + |1 - 0| = 1`
   
2. **Move 2**: `W` → `(-1, 1)`  
   - Manhattan Distance = `|-1 - 0| + |1 - 0| = 2`
   
3. **Move 3**: `S` → `(-1, 0)`  
   - Manhattan Distance = `|-1 - 0| + |0 - 0| = 1`
   
4. **Move 4**: `E` → `(0, 0)`  
   - Manhattan Distance = `|0 - 0| + |0 - 0| = 0`

At this point, we've made four moves, and the maximum Manhattan distance so far is `2`.

After changing `S` to `N` (since we are allowed to change up to `k=1` move), we get the string `NWNE`.

**New Steps**:
1. **Move 1**: `N` → `(0, 1)`  
   - Manhattan Distance = `1`
   
2. **Move 2**: `W` → `(-1, 1)`  
   - Manhattan Distance = `2`
   
3. **Move 3**: `N` → `(-1, 2)`  
   - Manhattan Distance = `3`
   
4. **Move 4**: `E` → `(0, 2)`  
   - Manhattan Distance = `2`

**Maximum Manhattan Distance**: `3`.

**Output**:  
The maximum Manhattan distance is `3`.

---

#### **Example 2:**

**Input**:  
`s = "NSWWEW"`, `k = 3`

- Start at `(0, 0)` (origin).
- Process the string character by character, updating the position and computing the Manhattan distance.

**Steps**:
1. **Move 1**: `N` → `(0, 1)`  
   - Manhattan Distance = `1`
   
2. **Move 2**: `S` → `(0, 0)`  
   - Manhattan Distance = `0`
   
3. **Move 3**: `W` → `(-1, 0)`  
   - Manhattan Distance = `1`
   
4. **Move 4**: `W` → `(-2, 0)`  
   - Manhattan Distance = `2`
   
5. **Move 5**: `E` → `(-1, 0)`  
   - Manhattan Distance = `1`
   
6. **Move 6**: `W` → `(-2, 0)`  
   - Manhattan Distance = `2`

At this point, we have completed all the moves. The maximum Manhattan distance so far is `2`.

Now, let's apply the allowed changes (`k = 3`):
- Change `S` to `N`, `E` to `W`, and `W` to `E`.
- The new string becomes `NNWWWW`.

**New Steps**:
1. **Move 1**: `N` → `(0, 1)`  
   - Manhattan Distance = `1`
   
2. **Move 2**: `N` → `(0, 2)`  
   - Manhattan Distance = `2`
   
3. **Move 3**: `W` → `(-1, 2)`  
   - Manhattan Distance = `3`
   
4. **Move 4**: `W` → `(-2, 2)`  
   - Manhattan Distance = `4`
   
5. **Move 5**: `W` → `(-3, 2)`  
   - Manhattan Distance = `5`
   
6. **Move 6**: `W` → `(-4, 2)`  
   - Manhattan Distance = `6`

**Maximum Manhattan Distance**: `6`.

**Output**:  
The maximum Manhattan distance is `6`.

---

### **Code**

```cpp
class Solution {
public:
    int maxDistance(string s, int k) {
        int maxDist = 0;
        int northMoves = 0, southMoves = 0, eastMoves = 0, westMoves = 0;

        for (char move : s) {
            // Update the movement counts based on the current direction
            if (move == 'N') northMoves++;
            else if (move == 'S') southMoves++;
            else if (move == 'E') eastMoves++;
            else westMoves++;

            // Calculate the number of opposite moves that cancel out
            int oppositeCancels = min(northMoves, southMoves) + min(eastMoves, westMoves);
            
            // Calculate the current Manhattan distance and maximize it
            maxDist = max(maxDist, northMoves + southMoves + eastMoves + westMoves - max(0, 2 * (oppositeCancels - k)));
        }
        
        return maxDist;
    }
};
```

---

### **Explanation of the Code**:

- We track the number of movements in each direction (`northMoves`, `southMoves`, `eastMoves`, `westMoves`).
- For each move in the string, we update the respective count and compute the number of opposite movements that cancel each other (`oppositeCancels`).
- We then calculate the Manhattan distance at each step, adjusting with the allowed changes `k`.
- The maximum Manhattan distance is stored and returned at the end.

---

### **Complexity Analysis**:

- **Time complexity**: `O(n)`, where `n` is the length of the string `s`. We are iterating through the string once, performing constant-time operations for each character.
  
- **Space complexity**: `O(1)`, since we are using a constant amount of extra space to store counters for movements in each direction.


['C++']