3443.K次修改后的最大曼哈顿距离

greedy, https://leetcode.cn/problems/maximum-manhattan-distance-after-k-changes/

给你一个由字符 '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 。

示例 3：

输入：s ="SN", k =0

输出: 1

解释：

因为SN两个方向会互相抵消，所以最大是1。此外，WE也会互相抵消。

提示：

1 <= s.length <= 10^5
0 <= k <= s.length
s 仅由 'N'、'S'、'E' 和 'W' 。

思路：贪心法，是尽量修改K次为两个方向不能互相抵消的两个字符。

思路：统计每个方向出现频次，找出最大两个频次。如果这两个不是互相抵消的方向，就尽量修改其他方向K次为这两个方向。如果这两个方向是互相抵消的，就修改次小频次的方向为频次大的方向，即每次距离+2;如果K还没有用完，再考虑修改其他方向。

python

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        # 初始化计数器和答案
        ce = cw = cn = cs = ans = 0
        
        for i, ch in enumerate(s):
            # 更新对应方向的计数
            if ch == "N": cn += 1
            elif ch == "S": cs += 1
            elif ch == "E": ce += 1
            else: cw += 1
            
            # 计算东西向和南北向的净位移
            bx = abs(ce - cw)
            by = abs(cn - cs)
            
            # 可抵消的最小步数
            px = min(ce, cw)
            py = min(cn, cs)
            
            # 计算基础距离加上最多k次转换后能增加的距离
            base = bx + by
            additional = min(k, px + py) * 2
            cand = base + additional
            
            # 更新最大距离，同时考虑当前索引i+1（因为enumerate从0开始）
            ans = max(ans, min(i + 1, cand))
        
        return ans

3443.K次修改后的最大曼哈顿距离 ​

3443.K次修改后的最大曼哈顿距离