Maximum Manhattan Distance After K Changes

Med

#3060Time: O(k * n^3). To compute each of the `O(n*k)` DP states, we may need to iterate over `O(i^2)` previous coordinate pairs, resulting in `O(n * k * n^2)` complexity.Space: O(k * n^3). The DP table stores sets of coordinates for each `(i, j)`. The number of distinct `(u,v)` pairs at step `i` can be `O(i^2)`, leading to a total space of `O(n * k * n^2)`.

Patterns

Math Counting

Data structures

Hash Table String

Prompt

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 (x_i, y_i) and (x_j, y_j) is |x_i - x_j| + |y_i - y_j|.

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 <= 10⁵
0 <= k <= s.length
s consists of only 'N', 'S', 'E', and 'W'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to explore all possible states. A state is defined by the number of moves made, the number of changes used, and the current coordinates. Due to the large state space, this method is highly inefficient and will not pass the given constraints, but it represents a brute-force way of exploring the solution space.

Algorithm

Define a DP state dp[i][j] as the set of all possible coordinate pairs (u, v) (where u=x+y, v=x-y) that can be reached after i moves using exactly j changes.
The base case is dp[0][0] containing the (u, v) pair from the first move s[0], and dp[0][1] containing the (u, v) pairs from changing s[0] to the other 3 directions.
To compute dp[i][j], we transition from states at i-1. For each (u_prev, v_prev) in dp[i-1][j], we calculate the new coordinates by applying the move s[i] without a change. For each (u_prev, v_prev) in dp[i-1][j-1], we calculate new coordinates by applying each of the 3 possible changed moves at s[i].
After filling the DP table, we iterate through all dp[i][j] for 0 <= i < n and 0 <= j <= k. For each (u, v) pair in these sets, we calculate the Manhattan distance max(|u|, |v|) and find the overall maximum.

Walkthrough

We can define a DP state dp[i][j] as the set of all possible coordinate pairs (u, v) (where u=x+y, v=x-y) that can be reached after i moves using exactly j changes. The coordinates u and v are used to simplify the Manhattan distance calculation, since |x| + |y| = max(|x+y|, |x-y|) = max(|u|, |v|). The DP table is built iteratively. To compute the states for i moves, we look at the reachable states after i-1 moves. A state at (i, j) can be reached from (i-1, j) by applying the original move s[i], or from (i-1, j-1) by applying a changed move at step i. The size of the sets of coordinates can grow polynomially with i, leading to a very high complexity. After populating the entire DP table, the maximum Manhattan distance is found by checking all reachable (u, v) pairs across all i and j.

1// The implementation for this DP approach is highly complex and memory-intensive,2// making it impractical for the given constraints. It would involve a multi-dimensional3// array of sets, e.g., Set<Pair<Integer, Integer>>[][] dp = new HashSet[n][k+1];4// and nested loops to populate it. Due to its infeasibility, a full code snippet5// is omitted.

Complexity

Time

O(k * n^3). To compute each of the `O(n*k)` DP states, we may need to iterate over `O(i^2)` previous coordinate pairs, resulting in `O(n * k * n^2)` complexity.

Space

O(k * n^3). The DP table stores sets of coordinates for each `(i, j)`. The number of distinct `(u,v)` pairs at step `i` can be `O(i^2)`, leading to a total space of `O(n * k * n^2)`.

Trade-offs

Pros

It's a straightforward (though complex) application of DP that exhaustively explores all possibilities.

Cons

Extremely high time and space complexity, making it infeasible for the given constraints.
Implementation is complex and prone to errors.

This approach is based on a key insight: the overall maximum Manhattan distance can be found by calculating the maximum possible distance at each specific point in time i (from 0 to n-1) and then taking the maximum of these values. For each timestamp i, we calculate the best possible outcome by optimally using up to k changes within the path prefix s[0...i]. This is a significant improvement over the brute-force DP, but it still involves redundant calculations.

Algorithm

Initialize max_dist = 0.
Loop with i from 0 to n-1 (representing the timestamp).
- Inside the loop, initialize u_orig = 0, v_orig = 0, and counts for different character groups (ne_count, sw_count, etc.) to zero.
- Start a nested loop with j from 0 to i.
  - Process s[j] to update u_orig, v_orig, and the character counts for the prefix s[0...i].
- After the inner loop, calculate the maximum and minimum possible u and v values at time i by using up to k changes.
  - max_u = u_orig + 2 * min(k, sw_count)
  - min_u = u_orig - 2 * min(k, ne_count)
  - max_v = v_orig + 2 * min(k, nw_count)
  - min_v = v_orig - 2 * min(k, se_count)
- Find the maximum Manhattan distance for time i: current_max = max(|max_u|, |min_u|, |max_v|, |min_v|).
- Update the overall max_dist = max(max_dist, current_max).
Return max_dist.

Walkthrough

The core idea is that max_{s'} max_i dist(i, s') = max_i max_{s'} dist(i, s'). This allows us to iterate through each possible final timestamp i and, for each one, determine the maximum Manhattan distance achievable at that specific time. We again use the u=x+y, v=x-y transformation.

For a fixed i, we can maximize |u_i| and |v_i| independently. To maximize u_i, we should change characters in s[0...i] that decrease u ('S', 'W') to characters that increase u ('N', 'E'). Each such change costs 1 and adds 2 to the final u_i. The number of such beneficial changes is limited by k and the number of 'S' or 'W' characters in the prefix. A similar logic applies to minimizing u_i, and maximizing/minimizing v_i.

The algorithm iterates i from 0 to n-1. In each iteration, it scans the prefix s[0...i] to compute the original (u, v) coordinates and count the number of characters of each type. This count is used to determine how many optimal changes can be made with a budget of k. Then, it calculates the maximum possible |u_i| and |v_i| and updates the global maximum distance.

1class Solution {2    public int maxManhattanDistance(String s, int k) {3        int n = s.length();4        long maxDist = 0;5 6        for (int i = 0; i < n; i++) {7            long u_orig = 0;8            long v_orig = 0;9            int ne_count = 0; // N, E10            int sw_count = 0; // S, W11            int nw_count = 0; // N, W12            int se_count = 0; // S, E13 14            for (int j = 0; j <= i; j++) {15                char move = s.charAt(j);16                if (move == 'N') {17                    u_orig++;18                    v_orig--;19                    ne_count++;20                    nw_count++;21                } else if (move == 'S') {22                    u_orig--;23                    v_orig++;24                    sw_count++;25                    se_count++;26                } else if (move == 'E') {27                    u_orig++;28                    v_orig++;29                    ne_count++;30                    se_count++;31                } else { // 'W'32                    u_orig--;33                    v_orig--;34                    sw_count++;35                    nw_count++;36                }37            }38 39            long max_u = u_orig + 2 * Math.min(k, sw_count);40            long min_u = u_orig - 2 * Math.min(k, ne_count);41            long max_v = v_orig + 2 * Math.min(k, nw_count);42            long min_v = v_orig - 2 * Math.min(k, se_count);43            44            long currentMax = Math.max(Math.abs(max_u), Math.abs(min_u));45            currentMax = Math.max(currentMax, Math.max(Math.abs(max_v), Math.abs(min_v)));46            47            maxDist = Math.max(maxDist, currentMax);48        }49        return (int) maxDist;50    }51}

Complexity

Time

O(n^2). The outer loop runs `n` times, and the inner loop for recalculating prefix information runs up to `n` times.

Space

O(1). We only use a few variables to store counts and intermediate results within the loops.

Trade-offs

Pros

Conceptually simpler than the DP approach and much more efficient.
Correctly identifies the core subproblem for each timestamp.
Requires only constant extra space.

Cons

The O(n^2) complexity is not optimal and will be too slow for constraints where n is up to 10^5.

This is the most efficient approach. It builds upon the previous one by optimizing the calculation of path coordinates and character counts. Instead of re-calculating these values from scratch for each timestamp i, we use running totals (a form of prefix sum) to compute them in O(1) time per step, leading to a linear time solution.

Algorithm

Initialize max_dist = 0.
Initialize running totals: u_orig = 0, v_orig = 0, ne_count = 0, sw_count = 0, nw_count = 0, se_count = 0.
Loop with i from 0 to n-1:
- Read character s[i] and update the six running totals in O(1) time.
- Calculate max_u, min_u, max_v, and min_v for the current prefix s[0...i] using the running totals and k.
- Update max_dist with the maximum Manhattan distance found so far.
Return max_dist.

Walkthrough

This approach uses the same core logic as the O(n^2) solution but eliminates the redundant work. The key optimization is to maintain running totals for all the necessary quantities as we iterate through the string s just once.

We need:

The original u coordinate (u_orig).
The original v coordinate (v_orig).
The count of 'S'/'W' characters (sw_count).
The count of 'N'/'E' characters (ne_count).
The count of 'N'/'W' characters (nw_count).
The count of 'S'/'E' characters (se_count).

In a single loop from i = 0 to n-1, we process s[i] and update these six values. At each step i, these variables will hold the correct values for the prefix s[0...i]. With these running totals, the calculation for max_u, min_u, max_v, and min_v for each i becomes an O(1) operation, making the entire algorithm O(n).

1class Solution {2    public int maxManhattanDistance(String s, int k) {3        int n = s.length();4        long maxDist = 0;5 6        long u_orig = 0;7        long v_orig = 0;8        long ne_count = 0; // Count of 'N' or 'E'9        long sw_count = 0; // Count of 'S' or 'W'10        long nw_count = 0; // Count of 'N' or 'W'11        long se_count = 0; // Count of 'S' or 'E'12 13        for (int i = 0; i < n; i++) {14            char move = s.charAt(i);15            if (move == 'N') {16                u_orig++;17                v_orig--;18                ne_count++;19                nw_count++;20            } else if (move == 'S') {21                u_orig--;22                v_orig++;23                sw_count++;24                se_count++;25            } else if (move == 'E') {26                u_orig++;27                v_orig++;28                ne_count++;29                se_count++;30            } else { // 'W'31                u_orig--;32                v_orig--;33                sw_count++;34                nw_count++;35            }36 37            // Maximize u = x+y38            long max_u = u_orig + 2 * Math.min(k, sw_count);39            // Minimize u = x+y40            long min_u = u_orig - 2 * Math.min(k, ne_count);41 42            // Maximize v = x-y43            long max_v = v_orig + 2 * Math.min(k, nw_count);44            // Minimize v = x-y45            long min_v = v_orig - 2 * Math.min(k, se_count);46            47            long currentMax = Math.max(Math.abs(max_u), Math.abs(min_u));48            currentMax = Math.max(currentMax, Math.max(Math.abs(max_v), Math.abs(min_v)));49            50            maxDist = Math.max(maxDist, currentMax);51        }52        return (int) maxDist;53    }54}

Complexity

Time

O(n). We iterate through the string once. All operations inside the loop are `O(1)`.

Space

O(1). We only use a constant number of variables to store the running totals, regardless of the input size.

Trade-offs

Pros

Optimal time complexity of O(n).
Optimal space complexity of O(1).
Solves the problem efficiently within the given constraints.

Cons

The logic involving the coordinate transformation (u=x+y, v=x-y) and the interchange of max operators can be non-obvious at first.

Solutions

Solution

1class Solution {2private3  char[] s;4private5  int k;6public7  int maxDistance(String s, int k) {8    this.s = s.toCharArray();9    this.k = k;10    int a = calc('S', 'E');11    int b = calc('S', 'W');12    int c = calc('N', 'E');13    int d = calc('N', 'W');14    return Math.max(Math.max(a, b), Math.max(c, d));15  }16private17  int calc(char a, char b) {18    int ans = 0, mx = 0, cnt = 0;19    for (char c : s) {20      if (c == a || c == b) {21        ++mx;22      } else if (cnt < k) {23        ++mx;24        ++cnt;25      } else {26        --mx;27      }28      ans = Math.max(ans, mx);29    }30    return ans;31  }32}

1class Solution {2public:3  int maxDistance(string s, int k) {4    auto calc = [&](char a, char b) {5      int ans = 0, mx = 0, cnt = 0;6      for (char c : s) {7        if (c == a || c == b) {8          ++mx;9        } else if (cnt < k) {10          ++mx;11          ++cnt;12        } else {13          --mx;14        }15        ans = max(ans, mx);16      }17      return ans;18    };19    int a = calc('S', 'E');20    int b = calc('S', 'W');21    int c = calc('N', 'E');22    int d = calc('N', 'W');23    return max({a, b, c, d});24  }25};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  char[] s;4private5  int k;6public7  int maxDistance(String s, int k) {8    this.s = s.toCharArray();9    this.k = k;10    int a = calc('S', 'E');11    int b = calc('S', 'W');12    int c = calc('N', 'E');13    int d = calc('N', 'W');14    return Math.max(Math.max(a, b), Math.max(c, d));15  }16private17  int calc(char a, char b) {18    int ans = 0, mx = 0, cnt = 0;19    for (char c : s) {20      if (c == a || c == b) {21        ++mx;22      } else if (cnt < k) {23        ++mx;24        ++cnt;25      } else {26        --mx;27      }28      ans = Math.max(ans, mx);29    }30    return ans;31  }32}

1class Solution {2public:3  int maxDistance(string s, int k) {4    auto calc = [&](char a, char b) {5      int ans = 0, mx = 0, cnt = 0;6      for (char c : s) {7        if (c == a || c == b) {8          ++mx;9        } else if (cnt < k) {10          ++mx;11          ++cnt;12        } else {13          --mx;14        }15        ans = max(ans, mx);16      }17      return ans;18    };19    int a = calc('S', 'E');20    int b = calc('S', 'W');21    int c = calc('N', 'E');22    int d = calc('N', 'W');23    return max({a, b, c, d});24  }25};

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.