📝 Beginner-Friendly Guide "Maximum Manhattan Distance After K Changes" LeetCode 3443 (C++ | Python

LeetCode 3443 | Medium | Greedy + Grid Simulation

🧠 Problem Summary

You are given:

A string s consisting of characters 'N', 'S', 'E', 'W'
An integer k representing the number of allowed direction changes

Each character represents a movement in the grid:

'N' = +1 on Y-axis
'S' = -1 on Y-axis
'E' = +1 on X-axis
'W' = -1 on X-axis

You start at the origin (0, 0). You may change at most k characters to any other direction. While simulating the movement from left to right, return the maximum Manhattan distance (|x| + |y|) that can be achieved at any point during this process.

🧹 Intuition

The key idea is:

At every point in the string, track how far we can get by using the allowed changes greedily.
Try different dominant directions (e.g., more North/East or more South/West) to maximize distance.
Simulate the path while spending up to k changes to redirect opposing steps in favor of the intended direction.

We attempt four directional pairs to greedily push our position to the farthest possible edge.

🧶 C++ Code

class Solution {
public:
    int maxDistance(string s, int k) {
        int ans = 0;
        char dir[4][2] = {{'N', 'E'}, {'N', 'W'}, {'S', 'E'}, {'S', 'W'}};

        for (auto d : dir) {
            int curr = 0, t = k;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == d[0] || s[i] == d[1]) {
                    if (t > 0) {
                        t--;
                        curr++;
                    } else {
                        curr--;
                    }
                } else {
                    curr++;
                }
                ans = max(ans, curr);
            }
        }
        return ans;
    }
};

📍 Key Notes:

Try different favorable directions using pairs (e.g., 'N'/'E') to maximize directional gain
Spend k changes where the direction doesn't align with the target
Greedy strategy with linear scan

Time Complexity: O(n)

Space Complexity: O(1)

💻 JavaScript Code

var maxDistance = function(s, k) {
    const directions = [['N', 'E'], ['N', 'W'], ['S', 'E'], ['S', 'W']];
    let maxDist = 0;

    for (const [d1, d2] of directions) {
        let curr = 0, rem = k;
        for (let i = 0; i < s.length; i++) {
            if (s[i] === d1 || s[i] === d2) {
                if (rem > 0) {
                    rem--;
                    curr++;
                } else {
                    curr--;
                }
            } else {
                curr++;
            }
            maxDist = Math.max(maxDist, curr);
        }
    }

    return maxDist;
};

🐍 Python Code

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        directions = [('N', 'E'), ('N', 'W'), ('S', 'E'), ('S', 'W')]
        ans = 0

        for d1, d2 in directions:
            curr = 0
            rem = k
            for ch in s:
                if ch == d1 or ch == d2:
                    if rem > 0:
                        rem -= 1
                        curr += 1
                    else:
                        curr -= 1
                else:
                    curr += 1
                ans = max(ans, curr)

        return ans

✅ Final Thoughts

This problem creatively blends grid simulation with greedy strategy:

Use directional biasing with limited changes
Track running distance to capture peak Manhattan distance
Efficient for up to 1e5 operations

It's a great example of how simulating variants of direction-based logic can be made optimal with smart preprocessing.

Drop a ❤️ if this helped, and keep building your algorithm intuition!

Happy Coding ✨

Om Shree @om_shree_0709