LeetCode 解題筆記：3614. Process String with Special Operations II

作者：王一哲
日期：2026年6月17日


LeetCode 題目連結：3614. Process String with Special Operations II

解題想法

困難題，3612. Process String with Special Operations I 的加強版，由於字串長度最長為 $10^{15}$，而且只要找出索引值 $k$ 的字元，要從每次的操作種類及操作後的長度逆推索引值 $k$ 的字元，如果直接操作字串會超時。

Python 程式碼

Runtime: 429 ms, beats 31.25%. Memory: 25.45 MB, beats 27.08%.

class Solution:
    def processStr(self, s: str, k: int) -> str:
        n = len(s)  # 字串長度
        L = [0] * n  # 第 i 個字元或操作時對應的 result 長度
        curr = 0  # 目前的 result 長度
        
        # --- 順向掃過 s 記錄長度 ---
        for i in range(n):
            if s[i] == '*':  # 刪除最後一個字元，長度減 1
                curr = max(0, curr - 1)
            elif s[i] == '#':  # 複製，長度加倍
                curr *= 2
            elif s[i] == '%':  # 反轉，長度不變
                pass
            else:  # 字母，長度加 1
                curr += 1
            L[i] = curr
        
        # --- 特例，索引值 k 超出最後的長度，回傳 .
        if k >= L[-1]: return "."

        # --- 逆向推導，找出索引值 k 對應的字母
        curr_k = k  # 目前的索引值
        for i in range(n-1, -1, -1):  # 由後往前找
            prev_len = L[i-1] if i > 0 else 0  # 第 i 次操作前一次的長度
            c = s[i]  # 字元 c
            if c == '*':  # 刪除最後一個字元，不影響原來合法的 curr_k
                continue
            elif c == '#':  # 複製，如果 curr_k 在複製後的右半邊，移回左半邊
                if curr_k >= prev_len:
                    curr_k -= prev_len
            elif c == '%':  # 反轉
                curr_k = prev_len - curr_k - 1
            else:  # 字母
                if curr_k == prev_len:  # 新增的字母
                    return c
        return "."  # 預設的回傳值

C++ 程式碼

Runtime: 35 ms, beats 35.63%. Memory: 49.32 MB, beats 20.69%.

class Solution {
public:
    char processStr(string s, long long k) {
        long long n = (long long)s.size(), curr = 0;  // 字串長度，目前的 result 長度
        vector<long long> L (n, 0);  // 第 i 個字元或操作時對應的 result 長度

        /* 順向掃過 s 記錄長度 */
        
        for(long long i = 0; i < n; i++) {
            char c = s[i];
            if (c == '*') {  // 刪除最後一個字元，長度減 1
                curr = max(0LL, curr - 1);
            } else if (c == '#') {  // 複製，長度加倍
                curr *= 2;
            } else if (c == '%') {  // 反轉，長度不變
                ;
            } else {  // 字母，長度加 1
                curr++;
            }
            L[i] = curr;
        }

        /* 特例，索引值 k 超出最後的長度，回傳 . */
        if (k >= L.back()) return '.';

        /* 逆向推導，找出索引值 k 對應的字母 */
        long long curr_k = k;  // 目前的索引值
        for(long long i = n-1; i >= 0; i--) {
            char c = s[i];
            long long prev_len = (i > 0 ? L[i-1] : 0);  // 第 i 次操作前一次的長度
            if (c == '*') {  // 刪除最後一個字元，不影響原來合法的 curr_k
                continue;
            } else if (c == '#') {  // 複製，如果 curr_k 在複製後的右半邊，移回左半邊
                if (curr_k >= prev_len) {
                    curr_k -= prev_len;
                }
            } else if (c == '%') {  // 反轉
                curr_k = prev_len - 1 - curr_k;
            } else {  // 字母
                if (curr_k == prev_len) {  // 新增的字母
                    return c;
                }
            }
        }
        return '.';  // 預設的回傳值
    }
};