#3443
Maximum Manhattan Distance After K Changes
specialist · 815 · lc medium +31 · premium · 54.2% accepted · 601 likes · top 46%
Description
You are given a string s consisting of the characters 'N', 'S', 'E', and 'W' encoding movements on an infinite grid:
- 'N': move north 1 unit.
- 'S': move south 1 unit.
- 'E': move east 1 unit.
- 'W': move west 1 unit.
Starting at the origin (0, 0), you may change at most k characters to any of the four directions.
Find the maximum Manhattan distance from the origin achievable at any point during the movement sequence.
The Manhattan distance between (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
Code
1
2
3