Position (x, y)Manhattan DistanceMaximums[0] == 'N'(0, 1)0 + 1 = 11s[1] == 'W'(-1, 1)1 + 1 = 22s[2] == 'N'(-1, 2)1 + 2 = 33s[3] == 'E'(0, 2)0 + 2 = 23

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

[{"language":"C++","code":"class Solution {\npublic:\n  int maxDistance(string s, int k) {\n    int n = s.size();\n    int north = 0, south = 0, east = 0, west = 0;\n    int maxDist = 0;\n    for (int i = 0; i < n; ++i) {\n      char ch = s[i];\n      if (ch == 'N') north++;\n      else if (ch == 'S') south++;\n      else if (ch == 'E') east++;\n      else if (ch == 'W') west++;\n      // Calculate possible changes for vertical and horizontal\n      int vert = abs(north - south);\n      int hori = abs(east - west);\n      int remK = k;\n      // Try to maximize vertical axis\n      int minVert = min(north, south);\n      int vertChange = min(remK, minVert);\n      vert += vertChange * 2;\n      remK -= vertChange;\n      // Try to maximize horizontal axis\n      int minHori = min(east, west);\n      int horiChange = min(remK, minHori);\n      hori += horiChange * 2;\n      // Update max distance\n      maxDist = max(maxDist, vert + hori);\n    }\n    return maxDist;\n  }\n};","lang":"cpp"},{"language":"Java","code":"public class Solution {\n\n    public int maxDistance(String s, int k) {\n        int maxDist = 0;\n        int north = 0, south = 0, east = 0, west = 0;\n        for (char ch : s.toCharArray()) {\n            // Update direction counters based on the current character\n            switch (ch) {\n                case 'N': north++; break;\n                case 'S': south++; break;\n                case 'E': east++; break;\n                case 'W': west++; break;\n            }\n            // Determine how many changes can be applied to vertical directions\n            int vertChanges = Math.min(Math.min(north, south), k);\n            // Use remaining changes for horizontal directions\n            int horiChanges = Math.min(Math.min(east, west), k - vertChanges);\n            // Update the maximum distance found so far\n            maxDist = Math.max(\n                maxDist,\n

Related Tags