输入#

字符串 s，整数 k

输出#

result[k]，若越界则返回 '.'

约束条件#

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

示例1#

1
input: s = "a#b%*", k = 1
2
output: "a"

解释：依次得到 "a" → "aa" → "aab" → "baa" → "ba"，下标 k = 1 的字符是 'a'

示例2#

1
input: s = "cd%#*#", k = 3
2
output: "d"

解释：依次得到 "c" → "cd" → "dc" → "dcdc" → "dcd" → "dcddcd"，下标 k = 3 的字符是 'd'

示例3#

1
input: s = "z*#", k = 0
2
output: "."

解释：依次得到 "z" → "" → ""，result 为空串，k = 0 越界，返回 '.'

从模拟出发#

Ⅰ 的做法很直接——用列表维护 result，从左到右模拟四种操作即可。若把同样思路搬到这里，在 s 较短时确实能过：

1
class Solution:
2
    def processStr(self, s: str, k: int) -> str:
3
        res = []
4
        for c in s:
5
            if c == '*':
6
                if res: res.pop()
7
            elif c == '#': res += res
8
            elif c == '%': res.reverse()
9
            else: res.append(c)
10
        return res[k] if k < len(res) else '.'

但本题 result 的长度可达 $10^{15}$，'#' 每次会把长度翻倍，字符串根本无法在内存中构造出来，模拟这条路走不通。

不过我们并不需要整个 result——只要第 k 个字符。能否在不展开字符串的前提下，把 k 映射回某个原始字母呢？

正向：只算长度#

构造完整字符串做不到，但追踪长度可以。从左到右扫一遍 s，用变量 sz 表示当前 result 的长度：

• 普通字母：sz += 1
• '*'：删除末尾，sz = max(sz - 1, 0)
• '#'：复制并拼接，sz += sz（长度翻倍）
• '%'：反转不改变长度，跳过

扫完后 sz 就是最终 result 的长度。若 k >= sz，直接返回 '.'。

以示例 1 为例，"a#b%*" 的长度变化为 $1 \to 2 \to 3 \to 3 \to 2$，最终 sz = 2，k = 1 合法。

反向：把 k 映射回去#

正向知道了「最终有多长」，接下来从右往左逆推每个操作对下标 k 的影响，同时维护「当前这一步操作之后 result 的长度」sz（从最终长度出发，逐步还原到操作前的长度）。

逆推时，四种操作的「撤销」规则如下：

'*'（撤销删除）
正向删除使长度减 1，撤销则 sz += 1。

'#'（撤销复制）
正向把长度为 sz/2 的串复制成 sz，撤销先 sz //= 2。复制后 result = 前半 + 后半，若 k 落在后半段（k >= sz），则 k -= sz，映射到前半段对应位置。

'%'（撤销反转）
反转不改变长度，但下标镜像：k = sz - k - 1。

普通字母
正向追加使长度加 1，撤销则 sz -= 1。若此时 k == sz，说明目标字符就是当前这个字母，直接返回。

以示例 1 演示逆推过程。最终 sz = 2，k = 1，从右往左处理 s：

示例 2 中 s = "cd%#*#"，正向得 sz = 6，k = 3。逆推时遇到 '#' 会将 k 从 3 调整为 0，再经 '%' 镜像为 1，最终在字母 'd' 处命中。

复杂度#

正向、反向各遍历 s 一次，时间复杂度 $O(n)$，空间复杂度 $O(1)$。

代码#

1
class Solution:
2
    def processStr(self, s: str, k: int) -> str:
3
        sz = 0
4
        for c in s:
5
            if c == '*':
6
                sz = max(sz - 1, 0)
7
            elif c == '#':
8
                sz += sz
9
            elif c == '%': continue
10
            else: sz += 1
11

12
        if k >= sz: return '.'
13

14
        for c in reversed(s):
15
            if c == '*': sz += 1
16
            elif c == '#':
17
                sz //= 2
18
                if k >= sz: k -= sz
19
            elif c == '%':
20
                k = sz - k - 1
21
            else:
22
                sz -= 1
23
                if k == sz: return c