You are given a string s consisting of characters 'N', 'S', 'E', and 'W', which represents a sequence of movements on a $2 ext{D}$ Cartesian plane starting from the origin $(0, 0)$. Each character corresponds to moving one unit in a specific direction:

• 'N' moves one unit north to $(x, y + 1)$

• 'S' moves one unit south to $(x, y - 1)$

• 'E' moves one unit east to $(x + 1, y)$

• 'W' moves one unit west to $(x - 1, y)$

You are also given an integer k. You can change at most k characters in s to any of the four directional characters.

Return the maximum Manhattan distance from the origin $(0, 0)$ that can be reached at any point while following the movements sequentially.

Note: The Manhattan distance between a point $(x, y)$ and the origin $(0, 0)$ is $|x| + |y|$.

Constraints:

• $1 \leq$ s.length $\leq 10^5$

• $0 \leq$ k $\leq$ s.length

• s consists of only 'N', 'S', 'E', and 'W'.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.