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 <= 1050 <= k <= s.lengths consists of only 'N', 'S', 'E', and 'W'.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.
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).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Modification | O(4^k * n) | O(1) | Useful only for conceptual understanding or very small k |
| Enumeration + Greedy | O(n) | O(1) | Best general solution; enumerates four quadrants and greedily converts up to k moves |
Maximum Manhattan Distance After K Changes | Detailed Explanation | Leetcode 3443 | codestorywithMIK • codestorywithMIK • 11,485 views views
Watch 9 more video solutions →Practice Maximum Manhattan Distance After K Changes with our built-in code editor and test cases.
Practice on FleetCode