Given a path of moves and the ability to change up to k moves, maximize the Manhattan distance reached at any point along the path.
You are given a string describing a walk on a 2D grid, where each character represents one unit move in one of the four cardinal directions. You may change the direction of at most k moves to any other direction.
After making up to k changes, consider the walk as it is executed from the origin one step at a time. Your task is to maximize the largest Manhattan distance from the origin reached at any prefix of the walk.
For a point (x, y), the Manhattan distance is |x| + |y|.
Return the maximum possible Manhattan distance achievable at some point during the walk after changing at most k moves.
Input Format
- A string
sof moves. - An integer
k, the maximum number of moves that may be changed. - Each character in
srepresents one move in the grid.
Output Format
- Return a single integer: the maximum Manhattan distance that can be reached at any prefix after at most
kchanges.
Constraints
1 <= |s| <= $10^{5}$0 <= k <= |s|- The move alphabet consists of the four cardinal directions.
- The exact platform constraints may vary; use these as practice constraints.
Example 1
Input
s = "NSEW", k = 1
Output
3
Explanation
Without changes, every prefix stays close to the origin. By changing one move to align with the best direction for a chosen prefix, the maximum reachable Manhattan distance at some prefix becomes 3.
Example 2
Input
s = "NNSS", k = 2
Output
4
Explanation
Change both S moves to N. Then the prefixes reach distances 1, 2, 3, 4, so the best possible value is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.