Greedy | C++ | Easy Approach
🏆 Maximum Manhattan Distance with K Changes | Greedy Approach 🚀📌 IntuitionThe problem requires us to find the maximum Manhattan distance we can achieve by makin
# 🏆 Maximum Manhattan Distance with K Changes | Greedy Approach 🚀  

## 📌 Intuition  
The problem requires us to find the **maximum Manhattan distance** we can achieve by making at most `k` modifications to the given movement string. The key observation is that **Manhattan distance is determined by the absolute sum of movements along the x-axis (east-west) and y-axis (north-south)**.  

To maximize the distance, we should try to **balance the movement counts** by converting weaker movements into their stronger counterparts using the available `k` changes.  

## 🔍 Approach  
1. **Count movements**  
   - Traverse the string and count occurrences of `'N'`, `'S'`, `'E'`, and `'W'`.  
   - Maintain variables `north`, `south`, `east`, and `west` to store their respective counts.  

2. **Adjust movements using `k` changes**  
   - If `north > south`, convert some `S` moves to `N` (or vice versa if `south > north`).  
   - If `west > east`, convert some `E` moves to `W` (or vice versa if `east > west`).  
   - The number of changes should be at most `k`, ensuring we maximize the absolute distance.  

3. **Compute the Manhattan Distance**  
   - The final Manhattan distance is given by **`|x| + |y|`**, where `x` and `y` are the final adjusted coordinates.  
   - Keep track of the maximum possible value during the traversal.  

## ⏳ Complexity Analysis  
- **Time Complexity**: **O(n)** → We iterate through the string once to count movements and then adjust the values in **constant time**.  
- **Space Complexity**: **O(1)** → Only a few integer variables are used for counting.  

## ✅ Code Implementation  

```cpp
class Solution {
public:
    int maxDistance(string s, int k) {
        int n = s.size();
        int y = 0,x=0,maxi =0,v = 0;
        int north = 0,south = 0,west = 0,east = 0;
        for(int i=0;i<n;i++) {
            v=k;
            if(s[i]=='N') north++;
            else if(s[i]=='S') south++;
            else if(s[i]=='E') east++;
            else west++;
            if(north>south) {
                int ch = min(v,south);
                y = north + (2*ch) - south;
                v -= ch;
            }
            else {
                int ch = min(v,north);
                y = south + (2*ch) - north;
                v-=ch;
            }
            if(west>east) {
                int ch = min(v,east);
                x = west + (2*ch) - east;
                v-=ch;
            }
            else {
                int ch = min(v,west);
                x = east + (2*ch) - west;
                v-=ch;
            }
            maxi = max(maxi,x+y);
        }
        return maxi;
    }
};

['Greedy', 'C++']