LeetCode 题解工作台
K 次修改后的最大曼哈顿距离
给你一个由字符 'N' 、 'S' 、 'E' 和 'W' 组成的字符串 s ，其中 s[i] 表示在无限网格中的移动操作： 'N' ：向北移动 1 个单位。 'S' ：向南移动 1 个单位。 'E' ：向东移动 1 个单位。 'W' ：向西移动 1 个单位。 初始时，你位于原点 (0, 0) 。你…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
我们可以枚举四种情况，分别为 , , , ，然后计算每种情况下的最大曼哈顿距离。 我们定义一个函数 $\text{calc}(a, b)$，用于计算最终生效方向为 和 时的最大曼哈顿距离。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：
'N'：向北移动 1 个单位。'S'：向南移动 1 个单位。'E'：向东移动 1 个单位。'W'：向西移动 1 个单位。
初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。
请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。
曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。
示例 1：
输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
| 移动操作 | 位置 (x, y) | 曼哈顿距离 | 最大值 |
|---|---|---|---|
| s[0] == 'N' | (0, 1) | 0 + 1 = 1 | 1 |
| s[1] == 'W' | (-1, 1) | 1 + 1 = 2 | 2 |
| s[2] == 'N' | (-1, 2) | 1 + 2 = 3 | 3 |
| s[3] == 'E' | (0, 2) | 0 + 2 = 2 | 3 |
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。
示例 2：
输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。
提示：
1 <= s.length <= 1050 <= k <= s.lengths仅由'N'、'S'、'E'和'W'。
解题思路
方法一：枚举 + 贪心
我们可以枚举四种情况，分别为 , , , ，然后计算每种情况下的最大曼哈顿距离。
我们定义一个函数 ，用于计算最终生效方向为 和 时的最大曼哈顿距离。
我们定义变量 用于记录当前的曼哈顿距离，定义 用于记录已经修改的次数，答案 初始化为 。
遍历字符串 ，如果当前字符为 或 ，则 加 ，否则如果 ，则 加 ，而 加 ，否则 减 。然后更新 。
最后返回四种情况下的最大值。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def maxDistance(self, s: str, k: int) -> int:
def calc(a: str, b: str) -> int:
ans = mx = cnt = 0
for c in s:
if c == a or c == b:
mx += 1
elif cnt < k:
cnt += 1
mx += 1
else:
mx -= 1
ans = max(ans, mx)
return ans
a = calc("S", "E")
b = calc("S", "W")
c = calc("N", "E")
d = calc("N", "W")
return max(a, b, c, d)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
They hint that NE, NW, SE, and SW are the only meaningful target shapes, which points to enumerating four cases instead of searching all edited strings.
- question_mark
They ask why the maximum can happen before the final move, which is a cue to score every prefix rather than only the whole string.
- question_mark
They push on how an edit changes distance, which is the key observation that flipping one harmful move to a helpful move gains 2.
常见陷阱
外企场景- error
Optimizing only the final position misses cases where an earlier prefix reaches a larger Manhattan distance than the completed walk.
- error
Trying to greedily edit characters in place can get messy because the best edit depends on the current prefix and chosen quadrant, not a single global replacement rule.
- error
Using a formula that adds only 1 per edit is wrong here because converting a harmful move into a helpful move removes one unit of loss and adds one unit of gain.
进阶变体
外企场景- arrow_right_alt
Return the edited string that achieves the maximum distance, which requires tracking reconstruction choices instead of only the score.
- arrow_right_alt
Allow different edit costs for changing vertical versus horizontal moves, which breaks the simple min(k, bad) math and needs weighted budgeting.
- arrow_right_alt
Ask for the maximum Euclidean distance instead of Manhattan distance, where the four-pair counting shortcut no longer fits as cleanly.