#3443

Medium

LeetCode Problem Workspace

Maximum Manhattan Distance After K Changes

Solve Maximum Manhattan Distance After K Changes by scanning prefixes and testing the four diagonal target pairs with limited edits.

hash table math string counting

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

Metric	Value
Time	O(n)
Space	O(1)

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.

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.

terminal

Solution

Solution 1: Enumeration + Greedy

We can enumerate four cases: $\textit{SE}$, $\textit{SW}$, $\textit{NE}$, and $\textit{NW}$, and then calculate the maximum Manhattan distance for each case.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        def calc(a: str, b: str) -> int:
            ans = mx = cnt = 0
            for c in s:
                if c == a or c == b:
                    mx += 1
                elif cnt < k:
                    cnt += 1
                    mx += 1
                else:
                    mx -= 1
                ans = max(ans, mx)
            return ans

        a = calc("S", "E")
        b = calc("S", "W")
        c = calc("N", "E")
        d = calc("N", "W")
        return max(a, b, c, d)

Continue Practicing

#3518 smallest palindromic rearrangement ii #3337 total characters in string after transformations ii #3335 total characters in string after transformations i