3614. Process String with Special Operations II

題目 / Problem

中文 給你一個字串 s，由小寫英文字母和三個特殊字元 '*'、'#'、'%' 組成，另外給一個整數 k。從左到右處理 s，逐步建立一個字串 result：

• 遇到小寫字母：把它接到 result 後面。
• 遇到 '*'：刪掉 result 的最後一個字元（若 result 為空則不動）。
• 遇到 '#'：把目前的 result 複製一份接在自己後面（長度變兩倍）。
• 遇到 '%'：把目前的 result 整個反轉。

回傳最終 result 的第 k 個字元（索引從 0 開始）。如果 k 超出範圍，回傳 '.'。

English You are given a string s of lowercase letters plus the special characters '*', '#', '%', and an integer k. Process s left to right to build result:

• A lowercase letter is appended to result.
• '*' removes the last character of result (does nothing if empty).
• '#' duplicates result and appends it to itself (length doubles).
• '%' reverses result.

Return the k-th character (0-indexed) of the final result, or '.' if k is out of bounds.

Constraints - 1 <= s.length <= 10^5 - s consists only of lowercase letters and '*', '#', '%'. - 0 <= k <= 10^15 - The final result length will not exceed 10^15.

Worked example s = "a#b%*", k = 1

Final result = "ba", index 1 is 'a'. Output: "a".

名詞解釋 / Glossary

• 索引 / Index (0-based)：第一個字元的位置是 0，第二個是 1，依此類推。所以「第 k 個」其實是第 k+1 個人類數法。 / Position counting that starts at 0; the "k-th character" means the one at offset k.
• 模運算 / Modulo (%)：a % b 是 a 除以 b 的餘數，例如 7 % 3 = 1。常用來把一個大索引「繞回」到較小範圍。 / The remainder of a / b; used here to wrap a large index back into a smaller range.
• 反向走查 / Backward walk：不真的建出字串，而是從最後一步往回推，逐步把「最終位置」翻譯回「更早的位置」。 / Instead of building the string, we trace operations in reverse, translating a final position into an earlier one.
• 64 位元整數 / 64-bit integer (long long)：一般 int 只能存到約 21 億，這題長度與 k 可達 10^15，必須用 long long（可存到約 9.2 × 10^18）。 / Lengths and k reach 10^15, far beyond a 32-bit int, so we need long long.
• malloc / free（C）：malloc 向系統要一塊記憶體（這裡用來放長度陣列），用完要用 free 還回去，否則記憶體洩漏。 / malloc requests heap memory; free returns it to avoid leaks.
• vector（C++）：可自動成長的動態陣列，會自己管理記憶體，不必手動 malloc/free。 / A self-managing dynamic array in C++; no manual memory handling.

思路

中文 最直覺的做法是真的照規則把 result 一個字元一個字元建出來，再取第 k 個。但 '#' 每次讓長度翻倍，最終長度可達 10^15——這麼長的字串根本放不進記憶體，暴力法直接出局。

關鍵觀察：我們其實不需要整個字串，只要那一個字元。所以分兩步。第一步「正向」掃過 s，只記錄每一步操作後的長度（不記內容）：字母 +1、'*' 在非空時 -1、'#' 變兩倍、'%' 不變。長度最多 10^15，用 long long 存得下，我把翻倍時加一個上限保護以防溢位（合法輸入永遠碰不到上限）。

第二步「反向」走查。我們手上有一個目標位置 pos（一開始 pos = k），意思是「在當前長度的字串裡，我要的字元在第 pos 格」。從最後一個操作往回推，每種操作都告訴我們：在它執行之前，同一個字元待在哪一格。'%'（反轉）：位置會鏡射，pos 變成 prevLen - 1 - pos。'#'（複製）：複製後的後半段就是前半段的翻版，所以 pos = pos % prevLen 就把後半的位置折回前半。'*'（刪除）：只動到最尾巴，我們要的位置在更前面，完全不受影響。字母：這一步在第 prevLen 格新增了這個字母——如果 pos 恰好等於 prevLen，那就是它，答案找到了；否則這個字母不是我們要的，pos 不變繼續往回。因為每個字元最終都是被某個字母步驟「生出來」的，反推一定會停在那一步。最後若 k 一開始就 ≥ 最終長度，直接回傳 '.'。

English The naive idea is to literally build result character by character and read index k. But '#' doubles the length each time, and the final length can be 10^15 — that string can never fit in memory, so brute force is impossible.

The key insight: we don't need the whole string, only one character. So we split the work in two. First, a forward pass scans s and records only the length after each operation (never the content): a letter adds 1, '*' subtracts 1 when non-empty, '#' doubles, '%' leaves length unchanged. Lengths fit in a long long; I clamp the doubling with a safety cap to avoid overflow (valid inputs never hit it).

Second, a backward walk. We keep a target position pos (starting at pos = k) meaning "the character I want sits at slot pos of the current string." Going from the last operation backward, each op tells us where that same character lived before the op ran. '%' (reverse) mirrors the position: pos becomes prevLen - 1 - pos. '#' (duplicate): the second half is a copy of the first, so pos = pos % prevLen folds a back-half position into the front. '*' (remove) only touches the very end, and our position is earlier, so it's untouched. A letter: this step inserted that letter at slot prevLen; if pos == prevLen, that letter is our answer — done. Otherwise pos is unchanged and we keep going. Since every character is ultimately produced by some letter step, the walk always lands on one. Finally, if k >= finalLen from the start, we return '.' immediately.

逐步走查 / Walkthrough

Input: s = "a#b%*", k = 1.

Forward pass — record length after each step / 正向記錄每步長度

finalLen = 2. Since k = 1 < 2, it is in bounds. Set pos = 1.

Backward walk — translate pos back / 反向把 pos 翻譯回去 (prevLen = length before this op = len[i-1], or 0 when i = 0)

Answer: 'a'. ✓

Solution — C

#include <stdlib.h>   // malloc / free
#include <string.h>   // strlen

// 演算法 / Algorithm:
// 1) 正向掃一遍 s，只記錄每步「操作後的長度」(不存內容)。
//    Forward pass: record only the length after each operation.
// 2) 反向走查，把目標位置 pos 一路翻譯回去，直到落在某個字母步驟。
//    Backward walk: map target position pos back until it lands on a letter step.

char processStr(char* s, long long k) {
    int n = (int)strlen(s);                 // s 的長度 / length of s
    // 配置長度陣列：len[i] = 處理完 s[i] 之後的長度
    // allocate array: len[i] = length after processing s[i]
    long long* len = (long long*)malloc(sizeof(long long) * n);

    const long long CAP = 2000000000000000LL; // 2e15 上限，防止翻倍時溢位 / cap to avoid overflow on doubling
    long long cur = 0;                        // 目前長度 / current length

    // ---- 正向：計算每一步的長度 / forward: compute each length ----
    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (c >= 'a' && c <= 'z') {           // 字母 → 長度 +1 / letter → length +1
            cur += 1;
        } else if (c == '*') {                // '*' → 非空時 -1 / remove one if non-empty
            if (cur > 0) cur -= 1;
        } else if (c == '#') {                // '#' → 長度翻倍 / duplicate doubles length
            cur *= 2;
            if (cur > CAP) cur = CAP;          // 夾住上限，合法輸入碰不到 / clamp; valid inputs never reach it
        }
        // c == '%' → 反轉不改變長度，cur 不動 / reverse keeps length, do nothing
        len[i] = cur;                         // 記下這一步後的長度 / store length after this step
    }

    long long finalLen = (n > 0) ? len[n - 1] : 0; // 最終長度 / final length
    if (k >= finalLen) {                       // k 超出範圍 / k out of bounds
        free(len);                             // 釋放記憶體 / release memory
        return '.';
    }

    long long pos = k;                         // 目前要找的位置 / position we are tracking
    char ans = '.';                            // 預設答案 / default answer

    // ---- 反向：把 pos 翻譯回更早的位置 / backward: translate pos to earlier positions ----
    for (int i = n - 1; i >= 0; i--) {
        // prevLen = 執行 s[i] 之前的長度 / length BEFORE op i
        long long prevLen = (i > 0) ? len[i - 1] : 0;
        char c = s[i];

        if (c >= 'a' && c <= 'z') {            // 字母步驟 / letter step
            // 這個字母被放在第 prevLen 格 / this letter sits at slot prevLen
            if (pos == prevLen) { ans = c; break; } // 命中即為答案 / a hit is the answer
            // 否則 pos < prevLen，字母非目標，pos 不變 / otherwise unaffected
        } else if (c == '*') {
            // 刪除只動最尾，pos 在更前面，不受影響 / remove touches only the end
        } else if (c == '#') {
            // 複製後的後半是前半翻版，用模運算折回 / fold back-half into front via modulo
            if (prevLen > 0) pos = pos % prevLen;
        } else if (c == '%') {
            // 反轉 → 位置鏡射 / reverse mirrors the position
            pos = prevLen - 1 - pos;
        }
    }

    free(len);                                 // 用完歸還記憶體 / free heap memory
    return ans;
}

Solution — C++

#include <string>
#include <vector>
using namespace std;

// 演算法 / Algorithm:
// 1) 正向掃 s，只記錄每步操作後的長度 (vector<long long>)。
//    Forward pass: store only post-op lengths.
// 2) 反向走查，把 pos 翻回去，落在某個字母步驟即為答案。
//    Backward walk: map pos back until it lands on a letter.

class Solution {
public:
    char processStr(string s, long long k) {
        int n = (int)s.size();                 // s 長度 / length of s
        vector<long long> len(n);              // vector：自動管理記憶體的動態陣列 / auto-managed dynamic array
        const long long CAP = 2'000'000'000'000'000LL; // 2e15 防溢位上限 / overflow-guard cap
        long long cur = 0;                     // 目前長度 / current length

        // ---- 正向計算長度 / forward length computation ----
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= 'a' && c <= 'z') cur += 1;            // 字母 +1 / letter +1
            else if (c == '*') { if (cur > 0) --cur; }     // '*' 非空時 -1 / remove if non-empty
            else if (c == '#') { cur *= 2; if (cur > CAP) cur = CAP; } // '#' 翻倍並夾上限 / double, clamped
            // '%' 反轉不改長度 / reverse keeps length
            len[i] = cur;                                  // 記錄 / record
        }

        long long finalLen = n ? len[n - 1] : 0;           // 最終長度 / final length
        if (k >= finalLen) return '.';                     // 超界回傳 '.' / out of bounds

        long long pos = k;                                 // 追蹤的位置 / tracked position

        // ---- 反向走查 / backward walk ----
        for (int i = n - 1; i >= 0; --i) {
            long long prevLen = i > 0 ? len[i - 1] : 0;    // 操作前長度 / length before op i
            char c = s[i];

            if (c >= 'a' && c <= 'z') {                    // 字母步驟 / letter step
                if (pos == prevLen) return c;              // 命中即回傳 / hit → answer
            } else if (c == '#') {
                if (prevLen > 0) pos %= prevLen;           // 模運算折回前半 / fold via modulo
            } else if (c == '%') {
                pos = prevLen - 1 - pos;                   // 反轉鏡射 / mirror on reverse
            }
            // c == '*' → 不影響 pos / does not affect pos
        }
        return '.';                                        // 理論上不會到這 / unreachable for valid input
    }
};

複雜度 / Complexity

• Time: O(n) — n 是 s 的長度。正向掃一遍 O(n)，反向走查再一遍 O(n)，每步都是常數時間。我們完全沒有真的建出長度可達 10^15 的字串，這正是能過的關鍵。 / One forward pass plus one backward pass, each step constant work; we never materialize the (up to 10^15-long) string.
• Space: O(n) — 只額外存一個長度陣列 len（n 個 long long）。 / One auxiliary array of n lengths; no character storage.

Pitfalls & Edge Cases

• 整數溢位 / Overflow：長度與 k 可達 10^15，超過 32 位元 int（約 2.1×10^9）。必須全程用 long long，否則翻倍會壞掉。 / Use long long everywhere; a 32-bit int overflows at ~2.1×10^9.
• '#' 用 % prevLen 而非 % len[i] / Modulo by the right length：折回時要對「複製前的長度」prevLen 取模，不是複製後的長度。對錯長度取模會算到錯誤位置。 / Fold back using the length before duplication, not after.
• prevLen > 0 的保護 / Guard against modulo by zero：若在空字串上遇到 '#'，prevLen 為 0，pos % 0 在 C/C++ 是未定義行為（會崩潰）。加判斷避開。 / pos % 0 is undefined behavior; skip when prevLen == 0.
• '*' 在空字串上不動 / '*' on empty does nothing：規則明說「若存在才刪」，所以 cur 為 0 時不要減成 -1。 / Don't let length go negative.
• 越界回傳 '.' / Out-of-bounds returns '.'：k 從 0 起算，合法範圍是 0 .. finalLen-1；k >= finalLen（含最終為空字串）都回傳 '.'，如範例 3。 / Index is 0-based; k >= finalLen (including an empty final string) yields '.'.
• 回傳型別是單一字元 / Return type is a single char：本題回傳的是 char 而非字串，別誤包成 "a" 字串。 / The signature returns a char, not a string.