AlgorithmAndLeetCode · pull · Jul 15, 2025 · Jul 15, 2025 · Jul 15, 2025 · Jul 15, 2025
diff --git a/Readme.md b/Readme.md
@@ -1184,6 +1184,7 @@
 [2999.Count-the-Number-of-Powerful-Integers](https://github.com/wisdompeak/LeetCode/tree/master/Recursion/2999.Count-the-Number-of-Powerful-Integers) (H-)      
 [3307.Find-the-K-th-Character-in-String-Game-II](https://github.com/wisdompeak/LeetCode/tree/master/Recursion/3307.Find-the-K-th-Character-in-String-Game-II) (M)      
 [3490.Count-Beautiful-Numbers](https://github.com/wisdompeak/LeetCode/tree/master/Recursion/3490.Count-Beautiful-Numbers) (M+)      
+[3614.Process-String-with-Special-Operations-II](https://github.com/wisdompeak/LeetCode/tree/master/Recursion/3614.Process-String-with-Special-Operations-II) (H-)      
 
 #### [Graph](https://github.com/wisdompeak/LeetCode/tree/master/Graph/)
 [332.Reconstruct-Itinerary](https://github.com/wisdompeak/LeetCode/tree/master/DFS/332.Reconstruct-Itinerary) (H)   

diff --git a/...cess-String-with-Special-Operations-II/3614.Process-String-with-Special-Operations-II.cpp b/...cess-String-with-Special-Operations-II/3614.Process-String-with-Special-Operations-II.cpp
@@ -0,0 +1,46 @@
+using ll = long long;
+class Solution {
+public:
+    char processStr(string s, long long k) {
+        k++;
+        int n = s.size();
+        s = "#"+s;
+        vector<ll>len(n+1);
+        const ll INF = 1e15+5;
+
+        for (int i=1; i<=n; i++) {
+            char c = s[i];
+            ll prev = len[i-1];
+            ll now = prev;
+            if ('a'<=c && c<='z')
+                now = prev+1;
+            else if (c == '*')
+                now = prev>0 ? (prev-1): 0;
+            else if (c=='#')
+                now = prev*2;
+            else if (c=='%')
+                now = prev;
+            len[i] = min(now, INF);                   
+        }
+        if (k==0 || k>(ll)len[n]) return '.';
+
+        for (int i=n; i>=1; i--) {
+            char c = s[i];
+            ll before = len[i-1];
+            ll after = len[i];
+            if ('a'<=c && c<='z') {
+                if (k==after)
+                    return c;
+            } else if (c=='*') {
+
+            } else if (c=='#') {
+                if (k>before)
+                    k-=before;
+            } else if ( c=='%') {
+                k = before-k+1;
+            }
+        }
+
+        return '.';
+    }
+};
diff --git a/Recursion/3614.Process-String-with-Special-Operations-II/Readme.md b/Recursion/3614.Process-String-with-Special-Operations-II/Readme.md
@@ -0,0 +1,13 @@
+### 3614.Process-String-with-Special-Operations-II
+
+很显然，构造完全之后的字符串非常长，我们不可能在此基础上定位第k个元素。此题极大概率是递归反推。
+
+我们分类思考每种操作下的第k个字符（注意是1-index）是什么情况：
+1. 添加一个字符，使得长度从a变成了a+1. 如果k=a+1，那么答案就是最新添加的字符。否则，递归求原字符串里的第k个。
+2. 删减最后一个字符，使得长度从a变成了a-1. 这种情况下k不可能是a（否则无解），因此等效于递归求原字符串里的第k个。
+3. 将字符串copy+append，使得长度从a变成了2a. 显然如果k<=a，递归求原字符串里的第k个。如果k>a，递归求原字符串里的第k-a个。
+4. 将字符串反转，长度依然是k。显然，递归求原字符串里的第a+1-k个。
+
+综上，只要知道每个回合的操作和长度变化，我们就可以把“求当前字符串的第k个元素”，逆推为“求前一个回合字符串的第k'个元素”，其中k'的计算如上。
+
+注意，这个题可能无解。逆推的前提是正向的变化合法存在。所以我们必须先正向走一遍，记录下每个回合的字符串长度，最后检查k是否在最终长度的范围内。