3443. Maximum Manhattan Distance After K Changes

Posted on Edited on In

3443. Maximum Manhattan Distance After K Changes

Description

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:

1
2
3
Input: s = "NWSE", k = 1

Output: 3

Explanation:

Change s[2] from 'S' to 'N'. The string s becomes "NWNE".

MovementPosition (x, y)Manhattan DistanceMaximum
s[0] == 'N'(0, 1)0 + 1 = 11
s[1] == 'W'(-1, 1)1 + 1 = 22
s[2] == 'N'(-1, 2)1 + 2 = 33
s[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:

1
2
3
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'.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int maxDistance(string s, int original_k) {
        int north = 0, south = 0, east = 0, west = 0, res = 0;
        // make 'N' and 'W' +1, and 'S' and 'E' -1, check max abs cur
        for (char& c : s) {
            int k = original_k;
            if (c == 'N') {
                north++;
            } else if (c == 'S') {
                south++;
            } else if (c == 'W') {
                west++;
            } else if (c == 'E') {
                east++;
            }
            int mx1 = max(north, south), mi1 = min(north, south);
            int mx2 = max(west, east), mi2 = min(west, east);
            if (k <= mi1) {
                mx1 += k;
                mi1 -= k;
                res = max(res, mx1 - mi1 + mx2 - mi2);
            } else {
                k -= mi1;
                mx1 += mi1;
                k = min(k, mi2);
                mx2 += k;
                mi2 -= k;
                res = max(res, mx1 + mx2 - mi2);
            }
            // cout << mx1 << " " << mi1 << " " << mx2 << " " << mi2 << " " << res << endl;
        }
        return res;
    }
};