Medium
题目描述
给你一个由字符 ‘U’、‘D’、‘L’ 和 ‘R’ 组成的字符串 s，表示在无限 2D 笛卡尔网格上的移动。
- ‘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。
你必须从 s 中选择并删除恰好一个长度为 k 的连续子串。然后，从坐标 (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 <= 10^5
- s 仅由 ‘U’、‘D’、‘L’ 和 ‘R’ 组成
- 1 <= k <= s.length
解题思路
这道题的关键思路是使用前缀和来高效计算删除任意长度为k的连续子串后的最终坐标。
核心分析：
- 将每个移动字符转化为坐标变化：‘U’→(0,1)，‘D’→(0,-1)，‘L’→(-1,0)，‘R’→(1,0)
- 如果我们删除区间[i, i+k-1]的子串，最终坐标就是前i个字符的移动 + 后面所有字符的移动
- 这等价于：总移动 - 被删除区间的移动
算法步骤：
- 计算每个位置的前缀和，得到prefix_x[i]和prefix_y[i]表示前i个字符在x轴和y轴上的累积移动
- 对于每个可能的删除起始位置i（0 ≤ i ≤ n-k），计算删除[i, i+k-1]后的最终坐标
- 最终坐标 = (总x移动 - 区间x移动, 总y移动 - 区间y移动)
- 使用哈希集合记录所有不同的最终坐标
时间复杂度优化： 通过前缀和，我们可以在O(1)时间内计算任意区间的移动量，整体时间复杂度为O(n)，比暴力模拟的O(n²)要好得多。
代码实现
class Solution {
public:
int distinctPoints(string s, int k) {
int n = s.length();
vector<int> prefix_x(n + 1, 0), prefix_y(n + 1, 0);
// 计算前缀和
for (int i = 0; i < n; i++) {
prefix_x[i + 1] = prefix_x[i];
prefix_y[i + 1] = prefix_y[i];
if (s[i] == 'U') prefix_y[i + 1]++;
else if (s[i] == 'D') prefix_y[i + 1]--;
else if (s[i] == 'L') prefix_x[i + 1]--;
else if (s[i] == 'R') prefix_x[i + 1]++;
}
set<pair<int, int>> distinct_points;
// 尝试删除每个长度为k的子串
for (int i = 0; i <= n - k; i++) {
int total_x = prefix_x[n];
int total_y = prefix_y[n];
int removed_x = prefix_x[i + k] - prefix_x[i];
int removed_y = prefix_y[i + k] - prefix_y[i];
int final_x = total_x - removed_x;
int final_y = total_y - removed_y;
distinct_points.insert({final_x, final_y});
}
return distinct_points.size();
}
};
class Solution:
def distinctPoints(self, s: str, k: int) -> int:
n = len(s)
prefix_x = [0] * (n + 1)
prefix_y = [0] * (n + 1)
# 计算前缀和
for i in range(n):
prefix_x[i + 1] = prefix_x[i]
prefix_y[i + 1] = prefix_y[i]
if s[i] == 'U':
prefix_y[i + 1] += 1
elif s[i] == 'D':
prefix_y[i + 1] -= 1
elif s[i] == 'L':
prefix_x[i + 1] -= 1
elif s[i] == 'R':
prefix_x[i + 1] += 1
distinct_points = set()
# 尝试删除每个长度为k的子串
for i in range(n - k + 1):
total_x = prefix_x[n]
total_y = prefix_y[n]
removed_x = prefix_x[i + k] - prefix_x[i]
removed_y = prefix_y[i + k] - prefix_y[i]
final_x = total_x - removed_x
final_y = total_y - removed_y
distinct_points.add((final_x, final_y))
return len(distinct_points)
public class Solution {
public int DistinctPoints(string s, int k) {
int n = s.Length;
int[] prefixX = new int[n + 1];
int[] prefixY = new int[n + 1];
// 计算前缀和
for (int i = 0; i < n; i++) {
prefixX[i + 1] = prefixX[i];
prefixY[i + 1] = prefixY[i];
if (s[i] == 'U') prefixY[i + 1]++;
else if (s[i] == 'D') prefixY[i + 1]--;
else if (s[i] == 'L') prefixX[i + 1]--;
else if (s[i] == 'R') prefixX[i + 1]++;
}
HashSet<(int, int)> distinctPoints = new HashSet<(int, int)>();
// 尝试删除每个长度为k的子串
for (int i = 0; i <= n - k; i++) {
int totalX = prefixX[n];
int totalY = prefixY[n];
int removedX = prefixX[i + k] - prefixX[i];
int removedY = prefixY[i + k] - prefixY[i];
int finalX = totalX - removedX;
int finalY = totalY - removedY;
distinctPoints.Add((finalX, finalY));
}
return distinctPoints.Count;
}
}
var distinctPoints = function(s, k) {
const n = s.length;
const prefixX = new Array(n + 1).fill(0);
const prefixY = new Array(n + 1).fill(0);
// 计算前缀和
for (let i = 0; i < n; i++) {
prefixX[i + 1] = prefixX[i];
prefixY[i + 1] = prefixY[i];
if (s[i]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 计算前缀和需要O(n)，遍历所有可能删除位置需要O(n-k+1)，总体为O(n) |
| 空间复杂度 | O(n) | 前缀和数组占用O(n)空间，哈希集合最多存储O(n)个不同坐标 |