# Maximum Manhattan Distance After K Changes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-manhattan-distance-after-k-changes)
Canonical: https://scaleengineer.com/dsa/problems/maximum-manhattan-distance-after-k-changes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
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
## Brute-Force Dynamic Programming
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.
**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)`.
**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.
### Explanation
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`.

```java
// 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.
```
### 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.

## Iterating Through Each Timestamp
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.
**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.
**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`.
### Explanation
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.

```java
class Solution {
    public int maxManhattanDistance(String s, int k) {
        int n = s.length();
        long maxDist = 0;

        for (int i = 0; i < n; i++) {
            long u_orig = 0;
            long v_orig = 0;
            int ne_count = 0; // N, E
            int sw_count = 0; // S, W
            int nw_count = 0; // N, W
            int se_count = 0; // S, E

            for (int j = 0; j <= i; j++) {
                char move = s.charAt(j);
                if (move == 'N') {
                    u_orig++;
                    v_orig--;
                    ne_count++;
                    nw_count++;
                } else if (move == 'S') {
                    u_orig--;
                    v_orig++;
                    sw_count++;
                    se_count++;
                } else if (move == 'E') {
                    u_orig++;
                    v_orig++;
                    ne_count++;
                    se_count++;
                } else { // 'W'
                    u_orig--;
                    v_orig--;
                    sw_count++;
                    nw_count++;
                }
            }

            long max_u = u_orig + 2 * Math.min(k, sw_count);
            long min_u = u_orig - 2 * Math.min(k, ne_count);
            long max_v = v_orig + 2 * Math.min(k, nw_count);
            long min_v = v_orig - 2 * Math.min(k, se_count);
            
            long currentMax = Math.max(Math.abs(max_u), Math.abs(min_u));
            currentMax = Math.max(currentMax, Math.max(Math.abs(max_v), Math.abs(min_v)));
            
            maxDist = Math.max(maxDist, currentMax);
        }
        return (int) maxDist;
    }
}
```
### 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`.

## Optimized Approach with Running Totals
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.
**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.
**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.
### Explanation
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:
1.  The original `u` coordinate (`u_orig`).
2.  The original `v` coordinate (`v_orig`).
3.  The count of 'S'/'W' characters (`sw_count`).
4.  The count of 'N'/'E' characters (`ne_count`).
5.  The count of 'N'/'W' characters (`nw_count`).
6.  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)`.

```java
class Solution {
    public int maxManhattanDistance(String s, int k) {
        int n = s.length();
        long maxDist = 0;

        long u_orig = 0;
        long v_orig = 0;
        long ne_count = 0; // Count of 'N' or 'E'
        long sw_count = 0; // Count of 'S' or 'W'
        long nw_count = 0; // Count of 'N' or 'W'
        long se_count = 0; // Count of 'S' or 'E'

        for (int i = 0; i < n; i++) {
            char move = s.charAt(i);
            if (move == 'N') {
                u_orig++;
                v_orig--;
                ne_count++;
                nw_count++;
            } else if (move == 'S') {
                u_orig--;
                v_orig++;
                sw_count++;
                se_count++;
            } else if (move == 'E') {
                u_orig++;
                v_orig++;
                ne_count++;
                se_count++;
            } else { // 'W'
                u_orig--;
                v_orig--;
                sw_count++;
                nw_count++;
            }

            // Maximize u = x+y
            long max_u = u_orig + 2 * Math.min(k, sw_count);
            // Minimize u = x+y
            long min_u = u_orig - 2 * Math.min(k, ne_count);

            // Maximize v = x-y
            long max_v = v_orig + 2 * Math.min(k, nw_count);
            // Minimize v = x-y
            long min_v = v_orig - 2 * Math.min(k, se_count);
            
            long currentMax = Math.max(Math.abs(max_u), Math.abs(min_u));
            currentMax = Math.max(currentMax, Math.max(Math.abs(max_v), Math.abs(min_v)));
            
            maxDist = Math.max(maxDist, currentMax);
        }
        return (int) maxDist;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxDistance(string s, int k) {
    auto 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 = max(ans, mx);
      }
      return ans;
    };
    int a = calc('S', 'E');
    int b = calc('S', 'W');
    int c = calc('N', 'E');
    int d = calc('N', 'W');
    return max({a, b, c, d});
  }
};

```

### Python

```python
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)

```