Problem Description

You are given a string s consisting of characters 'N', 'S', 'E', and 'W' that represent movements on an infinite grid. Starting from the origin (0, 0), each character tells you to move one unit in a specific direction:

• 'N': Move north (up) by 1 unit
• 'S': Move south (down) by 1 unit
• 'E': Move east (right) by 1 unit
• 'W': Move west (left) by 1 unit

You must execute these movements in the exact order they appear in the string. However, you can change at most k characters in the string to any of the four directions before starting the movement sequence.

Your goal is to find the maximum Manhattan distance from the origin that you can achieve at any point during your movement sequence. The Manhattan distance from the origin (0, 0) to any point (x, y) is calculated as |x| + |y|.

For example, if you have the string "NNE" and k = 1, you could change one 'N' to 'E' to get "ENE" or "NEE". As you execute the movements, you would track your position after each step and keep track of the maximum Manhattan distance reached at any point.

The key insight is that to maximize Manhattan distance, you want to move consistently in the same general direction. The solution considers four diagonal directions (SE, SW, NE, NW) and for each pair, treats movements in those two directions as beneficial (increasing distance) while movements in the opposite directions are detrimental (decreasing distance). When you have changes available (cnt < k), you can convert detrimental moves into beneficial ones.

Intuition

To maximize the Manhattan distance from the origin, we need to move as far as possible in a consistent direction. The Manhattan distance is |x| + |y|, which means we want to maximize the absolute values of our x and y coordinates.

Think about it geometrically - to get far from the origin, we should try to move diagonally rather than zigzagging back and forth. The four diagonal directions are: Northeast (NE), Northwest (NW), Southeast (SE), and Southwest (SW).

For example, if we're trying to maximize distance in the Southeast direction, both 'S' and 'E' movements are helpful - they increase our distance from the origin. Meanwhile, 'N' and 'W' movements work against us by bringing us closer to the origin.

Here's the key insight: we can use our k changes strategically. When we encounter a movement that goes against our chosen direction (like encountering 'N' when we want to go Southeast), we can change it to a favorable direction if we still have changes left. This converts a distance-reducing move into a distance-increasing move.

The greedy strategy emerges naturally: as we traverse the string in order, we keep track of our current Manhattan distance. When we see a favorable move ('S' or 'E' for Southeast), we increase our distance. When we see an unfavorable move and have changes remaining, we use a change to make it favorable. If we're out of changes, we have no choice but to execute the unfavorable move, decreasing our distance.

Since we don't know which diagonal direction will yield the maximum distance, we try all four possibilities: SE, SW, NE, and NW. Each attempt uses the same greedy strategy, and we return the maximum distance achieved across all four attempts.

The algorithm is efficient because it makes a single pass through the string for each direction pair, using a greedy approach to decide when to use our precious k changes for maximum benefit.

Learn more about Math patterns.

Solution Approach

The solution implements the greedy strategy by defining a helper function calc(a, b) that computes the maximum Manhattan distance when treating directions a and b as favorable.

Let's walk through the implementation step by step:

1. Helper Function calc(a, b):

This function takes two direction characters that represent our favorable directions (e.g., 'S' and 'E' for Southeast). It maintains three key variables:

• mx: Current Manhattan distance from origin
• cnt: Number of changes used so far
• ans: Maximum Manhattan distance achieved at any point

2. Processing Each Character:

As we traverse the string s character by character:

• Case 1: Favorable move (c == a or c == b):

  • Increment mx by 1 since this move takes us further from origin

• Case 2: Unfavorable move with changes available (cnt < k):

  • Use one change to convert this unfavorable move to favorable
  • Increment mx by 1 (as if it were favorable)
  • Increment cnt by 1 to track the used change

• Case 3: Unfavorable move with no changes left:

  • Must execute the unfavorable move as-is
  • Decrement mx by 1 since this brings us closer to origin

After processing each character, we update ans = max(ans, mx) to track the maximum distance achieved.

3. Trying All Four Diagonal Directions:

The main function calls calc four times:

• calc("S", "E"): Southeast direction
• calc("S", "W"): Southwest direction
• calc("N", "E"): Northeast direction
• calc("N", "W"): Northwest direction

4. Return Maximum:

The function returns the maximum value among all four attempts: max(a, b, c, d).

Time Complexity: O(n) where n is the length of string s, as we make four passes through the string.

Space Complexity: O(1) as we only use a constant amount of extra space.

The brilliance of this approach lies in its simplicity - by abstracting the problem to favorable vs unfavorable moves and using a greedy strategy to maximize distance at each step, we avoid complex state tracking while still finding the optimal solution.

Example Walkthrough

Let's walk through a concrete example with s = "NNESE" and k = 1.

We'll try the Southeast (SE) direction in detail, where 'S' and 'E' are favorable moves.

Initial state: Position = (0, 0), Manhattan distance = 0, changes used = 0

Step 1: Process 'N'

• 'N' is unfavorable for SE direction
• We have changes available (0 < 1)
• Use 1 change to convert 'N' → 'S' or 'E'
• Manhattan distance: 0 → 1
• Changes used: 0 → 1

Step 2: Process 'N'

• 'N' is unfavorable for SE direction
• No changes left (1 = 1)
• Must execute 'N' as-is (move north)
• Manhattan distance: 1 → 0
• Changes used: 1

Step 3: Process 'E'

• 'E' is favorable for SE direction
• Execute 'E' (move east)
• Manhattan distance: 0 → 1
• Changes used: 1

Step 4: Process 'S'

• 'S' is favorable for SE direction
• Execute 'S' (move south)
• Manhattan distance: 1 → 2
• Changes used: 1

Step 5: Process 'E'

• 'E' is favorable for SE direction
• Execute 'E' (move east)
• Manhattan distance: 2 → 3
• Changes used: 1

Result for SE direction: Maximum distance = 3

The algorithm would similarly try SW, NE, and NW directions:

• SW ('S', 'W'): Would change 'N' to favorable, but 'E' moves would hurt later → max = 1
• NE ('N', 'E'): Both 'N' and 'E' are favorable, only 'S' hurts → max = 3
• NW ('N', 'W'): Would change one 'E' or 'S' to favorable → max = 2

Final answer: max(3, 1, 3, 2) = 3

The key insight: by greedily using our change early when moving SE, we converted a distance-reducing move into a distance-increasing one, allowing us to build momentum in our chosen direction.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the calc function iterates through the entire string s once with a single loop, performing constant-time operations for each character. Since calc is called exactly 4 times (for the four different direction pairs), the total time complexity is 4 * O(n) = O(n).

The space complexity is O(1). The algorithm only uses a fixed number of variables (ans, mx, cnt in the calc function, and variables a, b, c, d in the main function) regardless of the input size. No additional data structures that scale with the input are created, so the space usage remains constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Greedy Strategy

The Problem: Many developers initially think that the greedy approach of always converting unfavorable moves to favorable ones (when k > 0) might miss optimal solutions. They worry about cases where "saving" changes for later might yield better results.

Why It Happens: The concern is that using changes early in the sequence might prevent us from using them at more critical points later.

The Reality: The greedy strategy actually IS optimal for this problem. Here's why:

• When moving in a consistent diagonal direction (e.g., SE), each favorable move adds +1 to distance
• Each unfavorable move subtracts -1 from distance
• Converting an unfavorable move to favorable creates a +2 swing in distance
• This +2 swing has the same value regardless of when it's applied in the sequence

Solution: Trust the greedy approach. Use changes as soon as you encounter unfavorable moves:

# Correct greedy approach
if direction == direction1 or direction == direction2:
    current_distance += 1
elif other_moves_count < k:  # Use change immediately when available
    other_moves_count += 1
    current_distance += 1
else:
    current_distance -= 1

Pitfall 2: Forgetting to Track Maximum Distance Throughout the Journey

The Problem: Some implementations only check the final distance after processing all moves, missing that the maximum might occur in the middle of the sequence.

Example Scenario:

• String: "NNNNSSSS" with k=2
• If we go North-East, after 4 N's we're at distance 4
• The subsequent S's will decrease our distance
• Final distance might be 0, but maximum was 4

Solution: Always update the maximum after processing each character:

for direction in s:
    # Process the move
    if direction == direction1 or direction == direction2:
        current_distance += 1
    # ... other cases ...
  
    # Critical: Update maximum after EVERY move, not just at the end
    max_distance = max(max_distance, current_distance)

Pitfall 3: Over-complicating with Actual Coordinate Tracking

The Problem: Attempting to track actual (x, y) coordinates and compute Manhattan distance at each step, which adds unnecessary complexity.

Why It's Unnecessary: The key insight is that when moving in a diagonal direction (e.g., SE), the Manhattan distance simply increases by 1 for each step in either of those directions. We don't need actual coordinates.

Incorrect Approach:

# Overly complex - tracking actual positions
x, y = 0, 0
for direction in s:
    if direction == 'N': y += 1
    elif direction == 'S': y -= 1
    elif direction == 'E': x += 1
    elif direction == 'W': x -= 1
    distance = abs(x) + abs(y)

Correct Simplified Approach:

# Just track distance changes
current_distance = 0
for direction in s:
    if direction in favorable_directions:
        current_distance += 1
    else:
        current_distance -= 1  # or +1 if we have changes left

Pitfall 4: Not Considering All Four Diagonal Directions

The Problem: Some solutions might only test one or two diagonal directions, missing the optimal solution that could come from a different diagonal.

Example: For string "EEENNNN", the NE diagonal would be optimal, but if you only tested SE and SW, you'd get a suboptimal result.

Solution: Always test all four diagonal combinations:

return max(
    calculate_max_distance("S", "E"),  # Southeast
    calculate_max_distance("S", "W"),  # Southwest
    calculate_max_distance("N", "E"),  # Northeast
    calculate_max_distance("N", "W")   # Northwest
)