CF1927B Following the String

Polycarp 丢失了一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成，但他还保留着该字符串的“迹”。 字符串 $s$ 的“迹”是一个长度为 $n$ 的整数数组 $a$，其中 $a_i$ 表示满足 $s_i = s_j$ 且 $j < i$ 的下标 $j$ 的个数。例如，字符串 abracadabra 的迹为 \[ 0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4 \]。 给定一个字符串的迹，请你构造出任意一个可能的原字符串 $s$。$s$ 仅能包含小写拉丁字母 a-z。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示丢失的字符串的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < n$），表示该字符串的迹。保证对于给定的迹，存在一个合适的字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个与给定迹对应的字符串 $s$。如果有多个满足条件的字符串，输出任意一个即可。 输出的字符串 $s$ 仅能包含小写拉丁字母 a-z。 保证每个测试用例都存在合法解。

由 ChatGPT 4.1 翻译