T3614.用特殊操作处理字符串 II

implementation, https://leetcode.cn/problems/process-string-with-special-operations-ii/

给你一个字符串 s，由小写英文字母和特殊字符：'*'、'#' 和 '%' 组成。

同时给你一个整数 k。

请根据以下规则从左到右处理 s 中每个字符，构造一个新的字符串 result：

• 如果字符是 小写 英文字母，则将其添加到 result 中。
• 字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
• 字符 '#' 会 复制 当前的 result 并追加到其自身后面。
• 字符 '%' 会 反转 当前的 result。

返回最终字符串 result 中第 k 个字符（下标从 0 开始）。如果 k 超出 result 的下标索引范围，则返回 '.'。

示例 1：

输入： s = "a#b%*", k = 1

输出： "a"

解释：

i	s[i]	操作	当前 result
0	'a'	添加 'a'	"a"
1	'#'	复制 result	"aa"
2	'b'	添加 'b'	"aab"
3	'%'	反转 result	"baa"
4	'*'	删除最后一个字符	"ba"

最终的 result 是 "ba"。下标为 k = 1 的字符是 'a'。

示例 2：

输入： s = "cd%#*#", k = 3

输出： "d"

解释：

i	s[i]	操作	当前 result
0	'c'	添加 'c'	"c"
1	'd'	添加 'd'	"cd"
2	'%'	反转 result	"dc"
3	'#'	复制 result	"dcdc"
4	'*'	删除最后一个字符	"dcd"
5	'#'	复制 result	"dcddcd"

最终的 result 是 "dcddcd"。下标为 k = 3 的字符是 'd'。

示例 3：

输入： s = "z*#", k = 0

输出： "."

解释：

i	s[i]	操作	当前 result
0	'z'	添加 'z'	"z"
1	'*'	删除最后一个字符	""
2	'#'	复制字符串	""

最终的 result 是 ""。由于下标 k = 0 越界，输出为 '.'。

提示:

• 1 <= s.length <= 10^5
• s 只包含小写英文字母和特殊字符 '*'、'#' 和 '%'。
• 0 <= k <= 10^15
• 处理 s 后得到的 result 的长度不超过 10^15。

我们可以使用逆向思维（Backward Simulation）来高效地解决这个问题。

算法思路

由于最终生成的字符串 result 长度可能高达 ${10}^{15}$，我们绝对不能直接构建这个字符串，这会导致内存溢出和超时。我们需要通过正向记录长度，反向推导字符的方法来解决：

1. 正向计算长度： 我们从左到右遍历字符串 s，模拟每一步操作后 result 的长度变化，并用一个数组 sizes 记录下每个位置 $i$ 执行操作 s[i] 后的当前长度 sz：

   • 如果 s[i] 是小写英文字母：长度加 1（即 sz += 1）。
   • 如果 s[i] == '*'：长度减 1（若当前长度大于 0，即 sz = max(0, sz - 1)）。
   • 如果 s[i] == '#'：长度翻倍（即 sz *= 2）。
   • 如果 s[i] == '%'：反转不改变长度（即 sz 不变）。

   如果遍历结束后的最终长度 sz 小于或等于 k，说明 k 越界，直接返回 '.'。

2. 反向推导对应字符： 因为我们知道最终 result 的第 k 个字符是由正向处理中的某个字母经过一系列操作（复制、反转、删除等）移动或留存下来的，我们可以从右到左遍历 s，逆向追踪这个 k 对应到之前状态中的新位置。

   在反向遍历时，我们通过 sizes[i] 知道在位置 $i$ 操作后 result 的实际长度 sz。我们根据 s[i] 的不同进行推导：

   • 如果 s[i] == '*'： 该操作删除了末尾字符。由于我们已通过正向计算获知了它对长度的影响，且由于 $k$ 能够留存下来，说明我们要找的字符不是在这个位置被删除的字符。因此，我们只需要简单地跳过 * 即可。

   • 如果 s[i] == '#'： 该操作将当前字符串复制并拼接到自身。拼接后的长度为 sz，前半部分的长度为 sz // 2。

     • 如果当前追踪的下标 $k\ge \text{sz}//2$，说明它落在拼接后的右半部分。根据对称性，它对应的就是左半部分（复制前）的 k - sz // 2。
     • 如果 $k<\text{sz}//2$，说明它就在左半部分，无须改变 $k$ 的位置。

   • 如果 s[i] == '%'： 该操作反转了字符串，长度为 sz。原本从左往右第 $k$ 个字符在反转前对应的下标为 sz - 1 - k。因此我们将 $k$ 映射为 sz - 1 - k。

   • 如果 s[i] 是小写字母： 该字母是在当前步骤被追加到 result 末尾的，即在当前长度为 sz 的字符串中，该字符的下标是 sz - 1。

     • 如果当前追踪的下标 $k$ 刚好等于 sz - 1，说明我们找到了源头字符，直接返回 s[i]。
     • 如果 $k<\text{sz}-1$，说明我们要找的字符在追加该字母之前就已经存在，不受此字母添加的影响，继续向左推导。

---

Python 3 实现代码

class Solution:
    def processStr(self, s: str, k: int) -> str:
        N = len(s)
        sz = 0
        sizes = [0] * N
        
        # 第一阶段：正向计算在每一步操作后的字符串长度
        for i, c in enumerate(s):
            if c == "*":
                if sz:
                    sz -= 1
            elif c == "#":
                sz *= 2
            elif c == "%":
                pass
            else:
                sz += 1
            sizes[i] = sz
            
        # 如果最终长度不足以覆盖索引 k，返回 '.'
        if k >= sz:
            return "."
            
        # 第二阶段：反向追踪下标 k 对应源字符的位置
        for i in reversed(range(N)):
            c = s[i]
            sz = sizes[i]
            
            if c == "*":
                # 跳过删除操作，因为我们只关心留存到最终状态的字符
                continue
            elif c == "#":
                # 拼接操作，若 k 落在右半部分，将其映射回左半部分
                if k >= sz // 2:
                    k -= sz // 2
            elif c == "%":
                # 反转操作，将 k 映射为其关于中心对称的位置
                k = sz - 1 - k
            else:
                # 字母添加操作
                # 若当前 k 刚好是最后添加的这个字母的位置，返回它
                if k == sz - 1:
                    return c

---

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 s 的长度。我们只需要正向和反向各遍历一次字符串 s，每次迭代内的操作均为常数级 $O(1)$ 时间。
• 空间复杂度：$O(N)$，用于存储长度数组 sizes。对于 $N\le {10}^5$，该空间消耗极小，能完美通过各项限制。