How to Solve Maximum Manhattan Distance After K Changes

The clean way to solve Maximum Manhattan Distance After K Changes is to evaluate each prefix against the four good direction pairs: NE, NW, SE, and SW. For any chosen pair, moves already in that pair help immediately, while opposite moves can be flipped using the edit budget to increase distance. This turns the problem into simple counting and math, giving an O(n) pass with constant extra space.

Problem Statement

You walk on an infinite grid following a string of moves made of N, S, E, and W, starting from the origin. Before executing the moves, you may change at most k characters so some steps point in more useful directions.

The goal is not the final position alone. You must maximize the Manhattan distance from the origin reached at any moment during the ordered walk, so the best answer may come from some prefix after using edits to avoid canceling vertical or horizontal progress.

Examples

Example 1

Input: s = "NWSE", k = 1

Output: 3

Change s[2] from 'S' to 'N' . The string s becomes "NWNE" . The maximum Manhattan distance from the origin that can be achieved is 3. Hence, 3 is the output.

Example 2

Input: s = "NSWWEW", k = 3

Output: 6

Change s[1] from 'S' to 'N' , and s[4] from 'E' to 'W' . The string s becomes "NNWWWW" . The maximum Manhattan distance from the origin that can be achieved is 6. Hence, 6 is the output.

Constraints

• 1 <= s.length <= 105
• 0 <= k <= s.length
• s consists of only 'N', 'S', 'E', and 'W'.

Solution Approach

Reduce the search to four diagonal plans

A maximum Manhattan distance prefix always benefits from pushing moves toward one diagonal quadrant, so brute force the four favorable pairs: NE, NW, SE, and SW. For each pair, treat those two letters as helpful moves and the other two letters as harmful because they reduce progress along that quadrant.

Count each prefix and spend edits where they add distance

As you scan the string, maintain counts of N, S, E, and W for the current prefix. For one chosen pair, let good be the number of moves already inside the pair and bad be the remaining prefix moves. Without edits, bad moves cancel progress, but each edit can convert one bad move into a good move and raise the Manhattan distance by 2 until you run out of bad moves or budget.

Compute the best prefix score directly

For a prefix of length len and one target pair, the best achievable distance is good - bad + 2 * min(k, bad), which is equivalent to len - 2 * bad + 2 * min(k, bad). Clamp naturally through min because you cannot fix more harmful moves than exist. Evaluate this formula for all four pairs at every prefix and keep the global maximum.

Complexity Analysis

The scan touches each character once, and each prefix is checked against only four fixed direction pairs, so the total time is O(n). The counts for N, S, E, and W plus a few integers are constant-size state, so the extra space is O(1).

What Interviewers Usually Probe

• They hint that NE, NW, SE, and SW are the only meaningful target shapes, which points to enumerating four cases instead of searching all edited strings.
• They ask why the maximum can happen before the final move, which is a cue to score every prefix rather than only the whole string.
• They push on how an edit changes distance, which is the key observation that flipping one harmful move to a helpful move gains 2.

Common Pitfalls or Variants

Common pitfalls

• Optimizing only the final position misses cases where an earlier prefix reaches a larger Manhattan distance than the completed walk.
• Trying to greedily edit characters in place can get messy because the best edit depends on the current prefix and chosen quadrant, not a single global replacement rule.
• Using a formula that adds only 1 per edit is wrong here because converting a harmful move into a helpful move removes one unit of loss and adds one unit of gain.

Follow-up variants

• Return the edited string that achieves the maximum distance, which requires tracking reconstruction choices instead of only the score.
• Allow different edit costs for changing vertical versus horizontal moves, which breaks the simple min(k, bad) math and needs weighted budgeting.
• Ask for the maximum Euclidean distance instead of Manhattan distance, where the four-pair counting shortcut no longer fits as cleanly.

How GhostInterview Helps

• It identifies the four-quadrant reduction quickly, so you stop overthinking hash maps of arbitrary positions and focus on prefix counts.
• It turns the edit effect into the exact +2 gain rule, which prevents the most common scoring mistake on this problem.
• It maps the problem to a compact O(n) formula tied to Maximum Manhattan Distance After K Changes, then checks the prefix logic against the sample walk.

Topic Pages

• Hash Table
• Math
• String
• Counting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern in Maximum Manhattan Distance After K Changes?

The core pattern is hash table plus math over prefixes. You count N, S, E, and W, then test the four diagonal direction pairs and use a direct formula for how many harmful moves can be repaired with k changes.

Why do we only test NE, NW, SE, and SW?

Manhattan distance grows when vertical and horizontal movement both favor one quadrant. Any best prefix can be viewed as trying to keep two directions and suppress their two opposites, so those four pairs cover all meaningful targets.

How does one change increase the score in this problem?

If a move currently hurts the chosen quadrant, changing it into a helpful move swings the prefix score by 2. You remove one unit of cancellation and add one unit of forward contribution.

Why is this O(n) even though we try multiple cases?

There are only four fixed cases, not a growing search space. For each character, you update counts once and evaluate four constant-time formulas, so the total work is linear in the string length.

Does this need an actual hash table implementation?

Not necessarily. The topic tag fits because you are counting direction frequencies, but in practice a four-counter array or four integer variables is enough since the alphabet is only N, S, E, and W.