3694. 刪除子字串後不同的終點

思路

題目要判斷忽略k個連續操作之後，可能的終點位置數量，這是典型的滑動窗口問題。
先算出忽略前面 0 ~ k 個操作後的位置，利用它再找出1 ~ k + 1 個操作後的位置，以此類推，直到終點。

因為unordered_set不能放pair（除非你自己寫一個哈希方法），
因此用long long去存兩個數字，為了避免負數存在，加入偏移量n確保座標都為正數。

最後的答案是unordered_set的大小，因此不需要真的把走到的確切座標算出，只需要知道偏移量就行，能省去一些時間。

程式碼

1. 滑動窗口

class Solution {
public:
    int distinctPoints(string s, int k) {
        int n = s.length();
        unordered_set<long long> uset;
        int x = 0, y = 0;
        for(int i = k; i < n; ++i) {
            if(s[i] == 'U') ++y;
            else if(s[i] == 'D') --y;
            else if(s[i] == 'L') --x;
            else ++x;
        }
        uset.insert(1LL * (x + n) << 32 | y + n); //忽略前 k 個操作的終點
        for(int i = k; i < n; ++i) {
            // 加入第 i - k操作
            if(s[i - k] == 'U') ++y;
            else if(s[i - k] == 'D') --y;
            else if(s[i - k] == 'L') --x;
            else ++x;
            // 忽略第 i 操作
            if(s[i] == 'U') --y;
            else if(s[i] == 'D') ++y;
            else if(s[i] == 'L') ++x;
            else --x;
            uset.insert(1LL * (x + n) << 32 | y + n);
        }
        return uset.size();
    }
};
/*
找到終點，
用滑窗刪掉幾個步驟，push 最後座標
*/

2.優化

class Solution {
public:
    int distinctPoints(string s, int k) {
        int n = s.length();
        unordered_set<long long> uset;
        uset.insert(1LL * n << 32 | n); // 初始偏移量。
        int x = 0, y = 0;
        for(int i = k; i < n; ++i) {
            // 加入操作
            if(s[i - k] == 'U') ++y;
            else if(s[i - k] == 'D') --y;
            else if(s[i - k] == 'L') --x;
            else ++x;
            // 恢復操作
            if(s[i] == 'U') --y;
            else if(s[i] == 'D') ++y;
            else if(s[i] == 'L') ++x;
            else --x;
            uset.insert(1LL * (x + n) << 32 | y + n);
        }
        return uset.size();
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$