How Far a Tweaked Route Can Take You

Medium

A robot starts at (0, 0) on an infinite grid and follows the commands in the string route one by one: N moves one cell up, S down, E right and W left. Before it starts, you may replace at most edits characters of the route with any of these four commands. Return the largest Manhattan distance from the origin that the robot can reach at any moment of the walk, not necessarily at the end. The Manhattan distance to (x, y) is |x| + |y|.

Example 1

route="NENSW", edits=1 → 4

Change the S to N to get NENNW. After the fourth step we are at (1, 3), distance 4.

Example 2

route="EWEW", edits=0 → 1

With no edits we just swing between (0, 0) and (1, 0), so the best is 1.

Example 3

route="SNSNWE", edits=2 → 5

Constraints

1 ≤ len(route) ≤ 10⁵
0 ≤ edits ≤ len(route)
route consists only of N, S, E, W

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math String Counting

Similar problems

Pieces With Matching Ends Medium The Growing String Medium Length of a Growing Word Hard Number in Roman Numerals Medium Fraction as a Decimal Medium

Input

route="NENSW", edits=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.