Skip to main content
Talentd

Maximum Manhattan Distance After K Changes - Solution & Explanation

MediumHash TableMathStringCounting11 min readAsked at: Microsoft, Meta, Uber +1
Practice this problem

Problem Statement

You are given a string s consisting of the characters 'N', 'S', 'E', and 'W', where s[i] indicates movements in an infinite grid:

  • 'N' : Move north by 1 unit.
  • 'S' : Move south by 1 unit.
  • 'E' : Move east by 1 unit.
  • 'W' : Move west by 1 unit.

Initially, you are at the origin (0, 0). You can change at most k characters to any of the four directions.

Find the maximum Manhattan distance from the origin that can be achieved at any time while performing the movements in order.

The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

 

Example 1:

Input: s = "NWSE", k = 1

Output: 3

Explanation:

Change s[2] from 'S' to 'N'. The string s becomes "NWNE".

Movement Position (x, y) Manhattan Distance Maximum
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3

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

Explanation:

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'.

Approach Overview

Problem Overview: You are given a string representing moves on a 2D grid using N, S, E, and W. You may change up to k characters to any direction. The goal is to maximize the Manhattan distance from the origin reached during the walk.

Approach 1: Brute Force Modification (Exponential Time)

One direct idea is to try all possible ways to modify up to k characters in the string. For each combination, simulate the walk and track the maximum Manhattan distance reached. The simulation itself is linear, but the number of possible modifications grows rapidly because each changed character can become one of four directions. This results in roughly O(4^k * n) time and O(1) extra space. This approach is mainly useful for reasoning about the problem or verifying small inputs.

Approach 2: Enumeration + Greedy (Optimal, O(n))

The Manhattan distance is |x| + |y|. The maximum distance occurs when moves push the position consistently toward one quadrant such as northeast or northwest. Instead of exploring all edits, enumerate the four diagonal directions: (N,E), (N,W), (S,E), and (S,W). For a chosen pair, treat moves that support that quadrant as beneficial and others as harmful.

Scan the string while counting beneficial and harmful moves. Harmful moves reduce the potential distance, but you can convert up to k of them into beneficial ones. Greedily apply these conversions to maximize the running score. Track the maximum distance seen during the traversal. Because only four direction pairs are tested and each scan is linear, the total complexity becomes O(4n) time and O(1) space.

This approach relies on simple string traversal and counting logic rather than heavy data structures. Some implementations also use small frequency counters or helper maps, connecting naturally with hash table techniques for direction checks.

Recommended for interviews: The Enumeration + Greedy approach is what interviewers expect. It shows that you recognize Manhattan distance can be maximized by pushing movement toward a quadrant and that limited modifications can be applied greedily. Mentioning the brute force idea first demonstrates problem exploration, but implementing the O(n) greedy enumeration shows strong algorithmic judgment.

Solution

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

We define a function calc(a, b) to calculate the maximum Manhattan distance when the effective directions are a and b.

We define a variable mx to record the current Manhattan distance, a variable cnt to record the number of changes made, and initialize the answer ans to 0.

Traverse the string s. If the current character is a or b, increment mx by 1. Otherwise, if cnt < k, increment mx by 1 and increment cnt by 1. Otherwise, decrement mx by 1. Then update ans = max(ans, mx).

Finally, return the maximum value among the four cases.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ModificationO(4^k * n)O(1)Useful only for conceptual understanding or very small k
Enumeration + GreedyO(n)O(1)Best general solution; enumerates four quadrants and greedily converts up to k moves

Video Solution

Maximum Manhattan Distance After K Changes | Detailed Explanation | Leetcode 3443 | codestorywithMIK • codestorywithMIK • 11,833 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Manhattan Distance After K Changes easy or hard?
The problem is generally classified as Medium difficulty. The implementation itself is straightforward, but recognizing that Manhattan distance can be maximized by pushing movement toward a specific quadrant requires a key greedy insight.
Maximum Manhattan Distance After K Changes Python/Java solution
Most implementations follow the same pattern: enumerate the four direction pairs, iterate through the string, and greedily apply up to k changes to unfavorable moves. This logic translates directly into Python, Java, C++, Go, TypeScript, or Rust with a simple loop and a few counters.
How to solve Maximum Manhattan Distance After K Changes in O(n)?
Enumerate the four quadrant directions such as (N,E) or (S,W). During a single pass of the string, treat moves matching the chosen pair as positive contributions and others as negative. Use up to k modifications to convert negative moves into positive ones and track the maximum distance achieved. Repeat for all four quadrants and take the best result.
What is the best approach for Maximum Manhattan Distance After K Changes?
The optimal method is Enumeration + Greedy. Enumerate the four diagonal movement directions (NE, NW, SE, SW) and treat moves that align with the chosen quadrant as beneficial. While scanning the string, convert up to k unfavorable moves into favorable ones to maximize the running Manhattan distance. This approach runs in O(n) time with O(1) space.
Is Maximum Manhattan Distance After K Changes asked at Google/Amazon/Meta?
Grid movement and Manhattan distance optimization problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving greedy decisions, coordinate movement, and string-based path simulation are especially common in mid-level algorithm interviews.
What data structure is used in Maximum Manhattan Distance After K Changes?
The solution mainly relies on string traversal and counting variables. Some implementations use small lookup structures or hash maps to check whether a move belongs to the current favorable direction set, but the algorithm works with constant auxiliary space.
What is the time complexity of Maximum Manhattan Distance After K Changes?
The optimal greedy enumeration solution runs in O(n) time because the string is scanned once for each of the four possible quadrant directions. Since 4 is constant, the complexity simplifies to linear time. Space complexity remains O(1) because only a few counters are maintained.

Ready to solve this problem?

Practice Maximum Manhattan Distance After K Changes with our built-in code editor and test cases.

Practice on FleetCode
Previous

As Far from Land as Possible