题解 | 偏爱的字符

import sys

def parse_input():
    sys.stdin.readline()
    preferred = set(sys.stdin.readline().strip().split())
    s = sys.stdin.readline().strip()
    return preferred, s

def solution(s: str, preferred: set) -> str:
    n = len(s)
    res = list(s)
    left = [-1] * n

    last = -1
    for i in range(n):
        if s[i] in preferred:
            last = i
        left[i] = last

    last = -1
    for i in reversed(range(n)):
        if s[i] in preferred:
            last = i
        if s[i] not in preferred:
            l = left[i]
            r = last
            if l == -1:
                res[i] = s[r]
            elif r == -1:
                res[i] = s[l]
            else:
                res[i] = s[l] if i - l <= r - i else s[r]
    
    return ''.join(res)

if __name__ == "__main__":
    preferred, s = parse_input()
    print(solution(s, preferred))