Maximum Manhattan Distance After K Changes

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

Examples

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

Solution

Method 1 - Greedy counting

Intuition

The Manhattan distance for a string of moves can be calculated as |count_N - count_S| + |count_E - count_W|, where each count represents the number of times a direction appears. Changing less frequent directions in either axis increases the distance, while changing more frequent ones decreases it. Only increasing the less frequent directions will maximize the Manhattan distance.

Approach

First, focus on modifying the less frequent vertical directions (N or S). If their count is greater than k, change only k of them; otherwise, change all and use any remaining modifications for the horizontal directions (E or W). Repeat this process for the horizontal axis with any leftover modifications. As you process the string, update and track the maximum Manhattan distance reached at any point.

Code

C++

class Solution {
public:
  int maxDistance(string s, int k) {
    int n = s.size();
    int north = 0, south = 0, east = 0, west = 0;
    int maxDist = 0;
    for (int i = 0; i < n; ++i) {
      char ch = s[i];
      if (ch == 'N') north++;
      else if (ch == 'S') south++;
      else if (ch == 'E') east++;
      else if (ch == 'W') west++;
      // Calculate possible changes for vertical and horizontal
      int vert = abs(north - south);
      int hori = abs(east - west);
      int remK = k;
      // Try to maximize vertical axis
      int minVert = min(north, south);
      int vertChange = min(remK, minVert);
      vert += vertChange * 2;
      remK -= vertChange;
      // Try to maximize horizontal axis
      int minHori = min(east, west);
      int horiChange = min(remK, minHori);
      hori += horiChange * 2;
      // Update max distance
      maxDist = max(maxDist, vert + hori);
    }
    return maxDist;
  }
};

Java

public class Solution {

    public int maxDistance(String s, int k) {
        int maxDist = 0;
        int north = 0, south = 0, east = 0, west = 0;
        for (char ch : s.toCharArray()) {
            // Update direction counters based on the current character
            switch (ch) {
                case 'N': north++; break;
                case 'S': south++; break;
                case 'E': east++; break;
                case 'W': west++; break;
            }
            // Determine how many changes can be applied to vertical directions
            int vertChanges = Math.min(Math.min(north, south), k);
            // Use remaining changes for horizontal directions
            int horiChanges = Math.min(Math.min(east, west), k - vertChanges);
            // Update the maximum distance found so far
            maxDist = Math.max(
                maxDist,
                calcDist(north, south, vertChanges) + calcDist(east, west, horiChanges)
            );
        }
        return maxDist;
    }

    // Compute the Manhattan distance for a pair of directions after applying modifications
    private int calcDist(int dir1, int dir2, int changes) {
        return Math.abs(dir1 - dir2) + changes * 2;
    }
}

Python

class Solution:
  def maxDistance(self, s: str, k: int) -> int:
    north = south = east = west = 0
    max_dist = 0
    for ch in s:
      if ch == 'N':
        north += 1
      elif ch == 'S':
        south += 1
      elif ch == 'E':
        east += 1
      elif ch == 'W':
        west += 1
      vert = abs(north - south)
      hori = abs(east - west)
      rem_k = k
      vert_change = min(rem_k, min(north, south))
      vert += vert_change * 2
      rem_k -= vert_change
      hori_change = min(rem_k, min(east, west))
      hori += hori_change * 2
      max_dist = max(max_dist, vert + hori)
    return max_dist

Complexity

• ⏰ Time complexity: O(n) for string traversal
• 🧺 Space complexity: O(1)