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.
s of moves.k, the maximum number of moves that may be changed.s represents one move in the grid.k changes.1 <= |s| <= $10^{5}$0 <= k <= |s|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
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.