Scale Engineer

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
MathCounting
Data structures
Hash TableString

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

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.

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

Solutions

class Solution {private  char[] s;private  int k;public  int maxDistance(String s, int k) {    this.s = s.toCharArray();    this.k = k;    int a = calc('S', 'E');    int b = calc('S', 'W');    int c = calc('N', 'E');    int d = calc('N', 'W');    return Math.max(Math.max(a, b), Math.max(c, d));  }private  int calc(char a, char b) {    int ans = 0, mx = 0, cnt = 0;    for (char c : s) {      if (c == a || c == b) {        ++mx;      } else if (cnt < k) {        ++mx;        ++cnt;      } else {        --mx;      }      ans = Math.max(ans, mx);    }    return ans;  }}

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 →

Next problem