3754 Maximum Manhattan Distance After K Changes
Maximum Manhattan Distance After K Changes 
You are given a string s consisting of the characters ‘N’, ‘S’, ‘E’, and ‘W’, where s[i] indicates movements in an infinite grid:
1
2
3
4
'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”.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
2
3
1 <= s.length <= 105
0 <= k <= s.length
s consists of only 'N', 'S', 'E', and 'W'.
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
class Solution:
def maxDistance(self, s: str, k: int) -> int:
ans = 0
north = south = east = west = 0
for it in s:
if it == "N":
north += 1
elif it == "S":
south += 1
elif it == "E":
east += 1
elif it == "W":
west += 1
times1 = min(north, south, k) # modification times for N and S
times2 = min(
east, west, k - times1
) # modification times for E and W
ans = max(
ans,
self.count(north, south, times1)
+ self.count(east, west, times2),
)
return ans
def count(self, drt1: int, drt2: int, times: int) -> int:
return (
abs(drt1 - drt2) + times * 2
) # Calculate modified Manhattan distance