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: Initially, you are at the origin (0, 0).
You are given a string s consisting of the characters 'N', 'S', 'E', and 'W', where s[i] indicates movements in an infinite grid:
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.
Example 1
Input: s = "NWSE", k = 1
Output: 3
Explanation: Change s[2] from 'S' to 'N' . The string s becomes "NWNE" . 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'.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.