跳转至

3694. 删除子字符串后不同的终点

题目描述

给你一个由字符 'U'、'D'、'L' 和 'R' 组成的字符串 s，表示在无限的二维笛卡尔网格上的移动。

  • 'U': 从 (x, y) 移动到 (x, y + 1)。
  • 'D': 从 (x, y) 移动到 (x, y - 1)。
  • 'L': 从 (x, y) 移动到 (x - 1, y)。
  • 'R': 从 (x, y) 移动到 (x + 1, y)。

你还得到了一个正整数 k。

你 必须 选择并移除 恰好一个 长度为 k 的连续子字符串 s。然后，从坐标 (0, 0) 开始，按顺序执行剩余的移动。

返回可到达的 不同 最终坐标的数量。

 

示例 1:

输入：s = "LUL", k = 1

输出：2

解释：

移除长度为 1 的子字符串后，s 可以是 "UL"、"LL" 或 "LU"。执行这些移动后，最终坐标将分别是 (-1, 1)、(-2, 0) 和 (-1, 1)。有两个不同的点 (-1, 1) 和 (-2, 0)，因此答案是 2。

示例 2:

输入：s = "UDLR", k = 4

输出：1

解释：

移除长度为 4 的子字符串后，s 只能是空字符串。最终坐标将是 (0, 0)。只有一个不同的点 (0, 0)，因此答案是 1。

示例 3:

输入：s = "UU", k = 1

输出：1

解释：

移除长度为 1 的子字符串后，s 变为 "U"，它总是以 (0, 1) 结束，因此只有一个不同的最终坐标。

 

提示:

  • 1 <= s.length <= 105
  • s 只包含 'U'、'D'、'L' 和 'R'。
  • 1 <= k <= s.length

解法

方法一：前缀和 + 哈希表

我们可以使用前缀和数组来记录每一步移动后的位置变化。 具体地，我们使用两个前缀和数组 \(f\) 和 \(g\) 分别记录每一步移动后在 \(x\) 轴和 \(y\) 轴上的位置变化。

初始化 \(f[0] = 0\) 和 \(g[0] = 0\)，表示初始位置为 \((0, 0)\)。然后，我们遍历字符串 \(s\)，对于每个字符：

  • 如果字符为 'U'，则 \(g[i] = g[i-1] + 1\)。
  • 如果字符为 'D'，则 \(g[i] = g[i-1] - 1\)。
  • 如果字符为 'L'，则 \(f[i] = f[i-1] - 1\)。
  • 如果字符为 'R'，则 \(f[i] = f[i-1] + 1\)。

接下来，我们使用一个哈希集合来存储不同的最终坐标。对于每个可能的子字符串移除位置 \(i\)（从 \(k\) 到 \(n\)），我们计算移除子字符串后的最终坐标 \((a, b)\)，其中 \(a = f[n] - (f[i] - f[i-k])\)，而 \(b = g[n] - (g[i] - g[i-k])\)。将坐标 \((a, b)\) 添加到哈希集合中。

最后，哈希集合的大小即为不同最终坐标的数量。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(s\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def distinctPoints(self, s: str, k: int) -> int:
        n = len(s)
        f = [0] * (n + 1)
        g = [0] * (n + 1)
        x = y = 0
        for i, c in enumerate(s, 1):
            if c == "U":
                y += 1
            elif c == "D":
                y -= 1
            elif c == "L":
                x -= 1
            else:
                x += 1
            f[i] = x
            g[i] = y
        st = set()
        for i in range(k, n + 1):
            a = f[n] - (f[i] - f[i - k])
            b = g[n] - (g[i] - g[i - k])
            st.add((a, b))
        return len(st)

 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
class Solution {
    public int distinctPoints(String s, int k) {
        int n = s.length();
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int x = 0, y = 0;
        for (int i = 1; i <= n; ++i) {
            char c = s.charAt(i - 1);
            if (c == 'U') {
                ++y;
            } else if (c == 'D') {
                --y;
            } else if (c == 'L') {
                --x;
            } else {
                ++x;
            }
            f[i] = x;
            g[i] = y;
        }
        Set<Long> st = new HashSet<>();
        for (int i = k; i <= n; ++i) {
            int a = f[n] - (f[i] - f[i - k]);
            int b = g[n] - (g[i] - g[i - k]);
            st.add(1L * a * n + b);
        }
        return st.size();
    }
}

 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
class Solution {
public:
    int distinctPoints(string s, int k) {
        int n = s.size();
        vector<int> f(n + 1), g(n + 1);
        int x = 0, y = 0;
        for (int i = 1; i <= n; ++i) {
            char c = s[i - 1];
            if (c == 'U')
                ++y;
            else if (c == 'D')
                --y;
            else if (c == 'L')
                --x;
            else
                ++x;
            f[i] = x;
            g[i] = y;
        }
        unordered_set<long long> st;
        for (int i = k; i <= n; ++i) {
            int a = f[n] - (f[i] - f[i - k]);
            int b = g[n] - (g[i] - g[i - k]);
            st.insert(1LL * a * n + b);
        }
        return st.size();
    }
};

 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
func distinctPoints(s string, k int) int {
    n := len(s)
    f := make([]int, n+1)
    g := make([]int, n+1)
    x, y := 0, 0
    for i := 1; i <= n; i++ {
        c := s[i-1]
        if c == 'U' {
            y++
        } else if c == 'D' {
            y--
        } else if c == 'L' {
            x--
        } else {
            x++
        }
        f[i] = x
        g[i] = y
    }
    st := make(map[int64]struct{})
    for i := k; i <= n; i++ {
        a := f[n] - (f[i] - f[i-k])
        b := g[n] - (g[i] - g[i-k])
        key := int64(a)*int64(n) + int64(b)
        st[key] = struct{}{}
    }
    return len(st)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function distinctPoints(s: string, k: number): number {
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    const g = new Array(n + 1).fill(0);
    let x = 0,
        y = 0;
    for (let i = 1; i <= n; ++i) {
        const c = s[i - 1];
        if (c === 'U') ++y;
        else if (c === 'D') --y;
        else if (c === 'L') --x;
        else ++x;
        f[i] = x;
        g[i] = y;
    }
    const st = new Set<number>();
    for (let i = k; i <= n; ++i) {
        const a = f[n] - (f[i] - f[i - k]);
        const b = g[n] - (g[i] - g[i - k]);
        st.add(a * n + b);
    }
    return st.size;
}

 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
use std::collections::HashSet;

impl Solution {
    pub fn distinct_points(s: String, k: i32) -> i32 {
        let n = s.len();
        let mut f = vec![0; n + 1];
        let mut g = vec![0; n + 1];
        let mut x = 0;
        let mut y = 0;
        let bytes = s.as_bytes();
        for i in 1..=n {
            match bytes[i - 1] as char {
                'U' => y += 1,
                'D' => y -= 1,
                'L' => x -= 1,
                _ => x += 1,
            }
            f[i] = x;
            g[i] = y;
        }
        let mut st = HashSet::new();
        let k = k as usize;
        for i in k..=n {
            let a = f[n] - (f[i] - f[i - k]);
            let b = g[n] - (g[i] - g[i - k]);
            st.insert((a as i64) * (n as i64) + (b as i64));
        }
        st.len() as i32
    }
}

评论