LeetCode 3443 - Maximum Manhattan Distance After K Changes

The input is a string s consisting of the four cardinal directions 'N', 'S', 'E', and 'W'. Starting from the origin (0, 0), we perform the moves one by one in the order given by the string.

leetcodemediumhash-tablemathstringcounting

LeetCode Problem 3443

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Counting

Solution

Problem Understanding

The input is a string s consisting of the four cardinal directions 'N', 'S', 'E', and 'W'. Starting from the origin (0, 0), we perform the moves one by one in the order given by the string. After every step, we can compute the Manhattan distance from the origin:

$|x|+|y|$

The goal is not necessarily to maximize the final distance after all moves. Instead, we want the largest distance reached at any intermediate moment while following the sequence.

Before executing the moves, we may modify at most k characters. Any modified character can become any of the four directions. These changes are chosen to maximize the greatest Manhattan distance encountered during the walk.

Since 1 ≤ n ≤ 10^5, any algorithm with quadratic complexity is too slow. We need a linear solution.

Several edge cases are important. If k = 0, we must use the original path. If k ≥ n, we can make all moves point in the same direction and obtain distance n. Another subtle point is that the answer may occur before the last move, so considering only the final position is insufficient.

Approaches

Brute Force

A naive approach would try every possible set of modifications and every replacement direction. For each resulting string, we could simulate the walk and record the maximum distance reached.

This approach is correct because it explicitly examines every possible modified path. Unfortunately, the number of possibilities grows exponentially. Even choosing which positions to modify already involves combinatorial complexity, and each modified position has four choices.

Therefore, brute force is infeasible for strings of length up to 10^5.

Key Observation

The Manhattan distance can be written as

$|x|+|y|=\max(x+y,x-y,-x+y,-x-y)$

Thus, maximizing Manhattan distance is equivalent to maximizing one of four linear expressions:

  • x + y
  • x - y
  • -x + y
  • -x - y

For a fixed expression, each direction contributes either +1 or -1.

For example, for x + y:

  • N contributes +1
  • E contributes +1
  • S contributes -1
  • W contributes -1

If a step contributes -1, changing that character into a favorable direction turns its contribution into +1, increasing the prefix sum by 2.

Therefore, for each prefix, if there are bad unfavorable moves, we may fix at most min(k, bad) of them. The resulting value becomes

prefix_sum + 2 * min(k, bad)

Evaluating this for all prefixes and for all four sign combinations yields the answer.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates all modifications
Optimal O(n) O(1) Scan four sign patterns

Algorithm Walkthrough

  1. Observe that Manhattan distance equals the maximum among four expressions: x+y, x-y, -x+y, and -x-y.
  2. Process each expression independently. For a chosen expression, determine which directions contribute +1. The remaining directions contribute -1.
  3. Traverse the string from left to right, maintaining two quantities:
  • current, the prefix sum using the original characters.
  • badCount, the number of steps in this prefix whose contribution is -1.
  1. Whenever a bad move appears, increment badCount.
  2. For the current prefix, we can change at most k bad moves. Each correction changes a contribution from -1 to +1, increasing the total by 2.
  3. Compute
candidate = current + 2 * min(k, badCount)
  1. Update the global answer with this candidate.
  2. Repeat the process for all four expressions and return the largest value found.

Why it works

For any fixed sign pattern, every move either helps or hurts the corresponding linear expression by exactly one unit. Changing a harmful move into a helpful move always provides a gain of 2, and there is no benefit in changing an already helpful move. Therefore, for a prefix containing badCount harmful moves, the best achievable value is obtained by fixing exactly min(k, badCount) of them. Since Manhattan distance is the maximum over the four sign patterns, examining all four guarantees the optimal answer.

Python Solution

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        patterns = [
            {"N", "E"},  # x + y
            {"N", "W"},  # -x + y
            {"S", "E"},  # x - y
            {"S", "W"}   # -x - y
        ]

        answer = 0

        for good_dirs in patterns:
            current = 0
            bad_count = 0

            for ch in s:
                if ch in good_dirs:
                    current += 1
                else:
                    current -= 1
                    bad_count += 1

                candidate = current + 2 * min(k, bad_count)
                answer = max(answer, candidate)

        return answer

The algorithm iterates over the four possible sign combinations. For each one, a set of favorable directions is stored.

During the scan, current represents the value of the corresponding linear expression using the original moves. Whenever a direction is unfavorable, it contributes -1 and increases bad_count.

At every prefix, we compute how much improvement is possible by converting up to k unfavorable moves into favorable ones. Since each conversion adds 2, the candidate value is

current + 2 * min(k, bad_count)

The maximum candidate over every prefix and every sign pattern becomes the answer.

Go Solution

func maxDistance(s string, k int) int {
	patterns := []map[byte]bool{
		{'N': true, 'E': true},
		{'N': true, 'W': true},
		{'S': true, 'E': true},
		{'S': true, 'W': true},
	}

	ans := 0

	for _, goodDirs := range patterns {
		current := 0
		badCount := 0

		for i := 0; i < len(s); i++ {
			if goodDirs[s[i]] {
				current++
			} else {
				current--
				badCount++
			}

			changeable := badCount
			if changeable > k {
				changeable = k
			}

			candidate := current + 2*changeable
			if candidate > ans {
				ans = candidate
			}
		}
	}

	return ans
}

The Go implementation follows the same logic. Maps with byte keys are used to represent the favorable directions for each sign pattern. All arithmetic uses ordinary integers, and overflow is not a concern because the answer is at most n, which is at most 10^5.

Worked Examples

Example 1

Input:

s = "NWSE"
k = 1

Consider the pattern x+y, whose favorable directions are {N, E}.

Step Char current badCount candidate
1 N 1 0 1
2 W 0 1 2
3 S -1 2 1
4 E 0 2 2

Now consider pattern -x+y, whose favorable directions are {N,W}.

Step Char current badCount candidate
1 N 1 0 1
2 W 2 0 2
3 S 1 1 3
4 E 0 2 2

The maximum value encountered is 3.

Output:

3

Example 2

Input:

s = "NSWWEW"
k = 3

The best pattern is -x+y, whose favorable directions are {N,W}.

Step Char current badCount candidate
1 N 1 0 1
2 S 0 1 2
3 W 1 1 3
4 W 2 1 4
5 E 1 2 5
6 W 2 2 6

The answer becomes 6.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Four linear scans
Space O(1) Only a few variables are maintained

Although there are four passes over the string, the const