题目描述

塔子哥天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。

题目思路

题目给定的字符串范围是$10^5$，只能使用线性时间的做法，可以直接考虑模拟。

考虑从左到右遍历和从右到左遍历，从左到右遍历时，维护一个距离当前下标最近的偏爱的字符的位置，对于非偏爱字符保存其最近的偏爱字符的位置。

同理，从右到左遍历时，也维护一个距离当前下标最近的偏爱字符的位置，与之前保存的左边最近的偏爱字符位置作比较即可得出答案。

代码