跳转至

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

题目描述

给你一个由字符 '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 <= 105
  • 0 <= k <= s.length
  • s 仅由 'N'、'S'、'E' 和 'W' 。

解法

方法一：枚举 + 贪心

我们可以枚举四种情况，分别为 \(\textit{SE}\), \(\textit{SW}\), \(\textit{NE}\), \(\textit{NW}\)，然后计算每种情况下的最大曼哈顿距离。

我们定义一个函数 \(\text{calc}(a, b)\)，用于计算最终生效方向为 \(\textit{a}\) 和 \(\textit{b}\) 时的最大曼哈顿距离。

我们定义变量 \(\textit{mx}\) 用于记录当前的曼哈顿距离，定义 \(\textit{cnt}\) 用于记录已经修改的次数，答案 \(\textit{ans}\) 初始化为 \(0\)。

遍历字符串 \(\textit{s}\)，如果当前字符为 \(\textit{a}\) 或 \(\textit{b}\)，则 \(\textit{mx}\) 加 \(1\)，否则如果 \(\textit{cnt} < k\)，则 \(\textit{mx}\) 加 \(1\)，而 \(\textit{cnt}\) 加 \(1\)，否则 \(\textit{mx}\) 减 \(1\)。然后更新 \(\textit{ans} = \max(\textit{ans}, \textit{mx})\)。

最后返回四种情况下的最大值。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(\textit{s}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    private char[] s;
    private int k;

    public int maxDistance(String s, int k) {
        this.s = s.toCharArray();
        this.k = k;
        int a = calc('S', 'E');
        int b = calc('S', 'W');
        int c = calc('N', 'E');
        int d = calc('N', 'W');
        return Math.max(Math.max(a, b), Math.max(c, d));
    }

    private int calc(char a, char b) {
        int ans = 0, mx = 0, cnt = 0;
        for (char c : s) {
            if (c == a || c == b) {
                ++mx;
            } else if (cnt < k) {
                ++mx;
                ++cnt;
            } else {
                --mx;
            }
            ans = Math.max(ans, mx);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxDistance(string s, int k) {
        auto calc = [&](char a, char b) {
            int ans = 0, mx = 0, cnt = 0;
            for (char c : s) {
                if (c == a || c == b) {
                    ++mx;
                } else if (cnt < k) {
                    ++mx;
                    ++cnt;
                } else {
                    --mx;
                }
                ans = max(ans, mx);
            }
            return ans;
        };
        int a = calc('S', 'E');
        int b = calc('S', 'W');
        int c = calc('N', 'E');
        int d = calc('N', 'W');
        return max({a, b, c, d});
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxDistance(s string, k int) int {
    calc := func(a rune, b rune) int {
        var ans, mx, cnt int
        for _, c := range s {
            if c == a || c == b {
                mx++
            } else if cnt < k {
                mx++
                cnt++
            } else {
                mx--
            }
            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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function maxDistance(s: string, k: number): number {
    const calc = (a: string, b: string): number => {
        let [ans, mx, cnt] = [0, 0, 0];
        for (const c of s) {
            if (c === a || c === b) {
                ++mx;
            } else if (cnt < k) {
                ++mx;
                ++cnt;
            } else {
                --mx;
            }
            ans = Math.max(ans, mx);
        }
        return ans;
    };
    const a = calc('S', 'E');
    const b = calc('S', 'W');
    const c = calc('N', 'E');
    const d = calc('N', 'W');
    return Math.max(a, b, c, d);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn max_distance(s: String, k: i32) -> i32 {
        fn calc(s: &str, a: char, b: char, k: i32) -> i32 {
            let mut ans = 0;
            let mut mx = 0;
            let mut cnt = 0;
            for c in s.chars() {
                if c == a || c == b {
                    mx += 1;
                } else if cnt < k {
                    mx += 1;
                    cnt += 1;
                } else {
                    mx -= 1;
                }
                ans = ans.max(mx);
            }
            ans
        }

        let a = calc(&s, 'S', 'E', k);
        let b = calc(&s, 'S', 'W', k);
        let c = calc(&s, 'N', 'E', k);
        let d = calc(&s, 'N', 'W', k);
        a.max(b).max(c).max(d)
    }
}

评论