LeetCode 3694. 刪除子字串後不同的終點（定長滑動視窗圖解）

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)，只有一個不同的點。

範例 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

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解與步驟說明為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左元素、多一個新元素，所以視窗內的總和可以用「加新的、減舊的」在 O(1) 內更新。這題的「和」不是一個數字，而是一個二維位移 (x, y)，做法一樣。前面幾篇已經用過，例如 2841 和 3439。

思路：終點的差別，只取決於被刪掉的那段位移

第一步：刪掉一段，相當於終點減去這段的位移

設不移除任何子字串時，最終座標是 (x, y)。

如果我們刪掉了子字串 "UR"，就是少走了一次「y 加一」和一次「x 加一」，所以最終座標是 (x − 1, y − 1)。

換個角度，站在最終座標的位置看，刪掉子字串後的偏移量是 (−1, −1)。

這個關係對每一種移除方式都成立：

最終座標 = 不刪除時的終點 (x, y) − 被刪掉那段的位移

第二步：不同終點 = 不同位移

(x, y) 是固定的，所以兩種移除方式的最終座標相不相同，完全取決於被刪掉那段的位移相不相同。問題因此變成：

對 s 中所有長為 k 的子字串，算出它們的位移 (dx, dy)，數有多少個不同的位移。

下面用 s = "UDRUR"、k = 2 實際走一遍。紅框是被移除的子字串，格子是座標平面（O 是起點），藍色圓點是這種移除方式的終點，綠色圈圈是之前已經出現過的終點，虛線框是不移除任何東西時的終點 (2, 1)。按「下一步」，注意最後兩種移除方式 "RU" 和 "UR"：順序不同，但位移都是 (1, 1)，所以終點相同，只算一個。

上一步 下一步 重置

s = "UDRUR"，k = 2：依序移除每一個長為 2 的子字串（紅框），看剩下的移動會走到哪裡

剩餘路徑經過的格子 這一步的終點 之前出現過的終點 不移除任何東西的終點

第三步：用定長滑動視窗算所有長為 k 的子字串位移

「所有長為 k 的子字串的位移」就是標準的定長滑動視窗：

1. 入：s[i] 進入視窗，位移加上 s[i] 的方向。
2. 若視窗還沒滿（長度不足 k），繼續。
3. 更新：把目前的位移 (x, y) 放進雜湊集合。
4. 出：s[i − k + 1] 離開視窗，位移減去它的方向，為下一個視窗做準備。

最後集合的大小就是答案。因為 (x, y) 是一對整數，Java 可以把它壓成一個 long 當作集合的元素，例如 (long) (x + n) << 20 | (y + n)（+ n 避免負數）。

兩種寫法的差別只在於要不要「真的算出第一個視窗的位移」：

• 優化前：照模板算每一個視窗的位移。
• 優化後：因為終點只和位移的差有關，所以只算「後續視窗相對第一個視窗的增減量」，第一個視窗直接當 (0, 0)。

方法一：優化前（直接算每個視窗的位移）

思路

1. 方向表 DIRS：L → (−1, 0)、R → (1, 0)、D → (0, −1)、U → (0, 1)。
2. i 往右走，s[i] 進入視窗：x += DIRS[c][0]、y += DIRS[c][1]。
3. 若視窗還沒滿（left = i + 1 − k < 0），繼續。
4. 把目前的位移放進集合 set。
5. s[left] 離開視窗：x、y 各自減去它的方向。

圖解（可互動）

用 s = "UDRUR"、k = 2。視窗位移依序是 "UD" → (0, 0)、"DR" → (1, −1)、"RU" → (1, 1)、"UR" → (1, 1)，最後一個重複，集合大小是 3。

上一步 下一步 重置

s = "UDRUR"，k = 2：視窗內移動的位移 (x, y)，放進集合

視窗位移 (x, y)(0, 0)

集合大小 set.size()0

解法（灵茶山艾府）

class Solution {
    private static final int[][] DIRS = new int[128][];

    static {
        DIRS['L'] = new int[]{-1, 0};
        DIRS['R'] = new int[]{1, 0};
        DIRS['D'] = new int[]{0, -1};
        DIRS['U'] = new int[]{0, 1};
    }

    public int distinctPoints(String s, int k) {
        int n = s.length();
        Set<Long> set = new HashSet<>();
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            // 1. 入
            char c = s.charAt(i);
            x += DIRS[c][0];
            y += DIRS[c][1];

            int left = i + 1 - k; // 視窗左端點
            if (left < 0) { // 視窗大小不足 k
                continue;
            }

            // 2. 記錄答案
            // 把兩個 int 壓縮到一個 long 中，+n 避免負數
            set.add((long) (x + n) << 20 | (y + n)); // 測試發現 << 20 比 << 32 快很多

            // 3. 出，為下一個視窗做準備
            char out = s.charAt(left);
            x -= DIRS[out][0];
            y -= DIRS[out][1];
        }
        return set.size();
    }
}

複雜度分析

• 時間複雜度：O(n)，其中 n 是 s 的長度。
• 空間複雜度：O(n − k)。有 n − k + 1 個視窗，所以雜湊表中至多保存 n − k + 1 個不同座標。

方法二：優化（只算相對第一個視窗的增減量）

思路

所有視窗都可以由第一個視窗推出來，所以只需要算相對第一個視窗的增減量：

• 增減量不同，位移就不同，最終座標也就不同。
• 因此不需要算第一個視窗的位移，直接把它的增減量記為 (0, 0)。
• 後續視窗右移一格時，增減量 += 新進入字元的方向 − 離開字元的方向，把它放進集合。

這樣迴圈從 i = k 開始，省掉了初始累加和「視窗還沒滿」的判斷。

圖解（可互動）

同樣用 s = "UDRUR"、k = 2。注意這裡看到的 (x, y) 是相對第一個視窗的差，和方法一的位移相差一個固定的量，但「是否重複」的結果完全一樣，集合大小同樣是 3。

上一步 下一步 重置

s = "UDRUR"，k = 2：只記錄「相對第一個視窗的增減量」，第一個視窗固定是 (0, 0)

相對第一個視窗的增減量 (x, y)(0, 0)

集合大小 set.size()1

解法（灵茶山艾府）

class Solution {
    private static final int[][] DIRS = new int[128][];

    static {
        DIRS['L'] = new int[]{-1, 0};
        DIRS['R'] = new int[]{1, 0};
        DIRS['D'] = new int[]{0, -1};
        DIRS['U'] = new int[]{0, 1};
    }

    public int distinctPoints(String s, int k) {
        int n = s.length();
        int x = 0, y = 0;
        Set<Long> set = new HashSet<>();
        set.add((long) n << 20 | n); // 第一個視窗
        for (int i = k; i < s.length(); i++) {
            char in = s.charAt(i);
            char out = s.charAt(i - k);
            x += DIRS[in][0] - DIRS[out][0];
            y += DIRS[in][1] - DIRS[out][1];
            set.add((long) (x + n) << 20 | (y + n));
        }
        return set.size();
    }
}

這裡 set.add((long) n << 20 | n) 就是把 (0, 0) 用同樣的壓縮方式（+ n）放進集合。

複雜度分析

• 時間複雜度：O(n − k)，其中 n 是 s 的長度。
• 空間複雜度：O(n − k)。有 n − k + 1 個視窗，所以雜湊表中至多保存 n − k + 1 個不同座標。