给定长度为 n 的数组 a1,…,an。要求构造只含小写字母的字符串 s1…sn,并满足:
由题意保证数据合法且所需不同字符数不超过 26。
核心思路(贪心/直接构造):
给定一个长度为 n 的数组 {a1,a2,...,an} 。请你构造一个长度为 n、仅由小写字母构成的字符串 s ,满足对每一个位置 i(1≤i≤n):
若 ai=0 ,则 si 在位置 [1,i−1] 中从未出现过;
若 ai>0,则 1≤ai<i ,并且 si=sai ,同时在所有 ai<j<i 的位置上均满足 sj=sai (即 ai 的确是 si 的上一个出现位置)。
换言之,ai 给出了 si 的“上一个相同字符的位置”(若不存在则为 0)。保证输入一定合法,即存在至少一个满足条件的子符串。
第一行输入一个整数 n(1≤n≤2×105) 表示字符串长度。
第二行输入 n 个整数 a1,a2,...,an(0≤ai<i) 表示数组 a 。并保证所有 ai 构成若干条严格指向更小下标的“链”,从而对应某个可行字符串。
除此之外,保证输入的数据满足:存在一个仅由小写英文字母构成的解(即构造所需的独立字符数量不超过 26 )
输出一行,一个长度为 n 的字符串 s 。
如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
输入
10
0 0 1 2 0 5 3 7 0 9
输出
ababccaadd
说明
设输出字符串 s="ababccaadd",对应关系如下(下标从 1 开始):
i=1,a1=0,s1=′a′ 为新字符;
i=2,a2=0,s2=′b′ 为新字符;
i=3,a3=1,s3=s1=′a′,且在位置 2 处与 ′a′ 不同;
i=4,a4=2,s4=s2=′b′,且在位置 3 处与 ′b′ 不同;
i=5,a5=0,s5=′c′ 为新字符;
i=6,a6=5,s6=s5=′c′;
i=7,a7=3,s7=s3=′a′;
i=8,a8=7,s8=s7=′a′;
i=9,a9=0,s0=′d′ 为新字符;
i=10,a10=9,s10=s9=′d′ 。
逐一核对可知,ai 确为 si 的上一次出现位置(无则为 0),满足题意。