偏爱的字符

[题目链接](https://www.nowcoder.com/practice/294da7ea5f184655a31bf659035fc874)

思路

对于每个非偏爱字符，需要找到距离它最近的偏爱字符来替换。如果距离相同则选左边的。

暴力做法是对每个位置扫描整个字符串找最近偏爱字符，时间复杂度 。可以用两遍扫描优化到 ：

1. 从左到右扫描：记录每个位置左边（含自身）最近的偏爱字符位置 left[i]。
2. 从右到左扫描：记录每个位置右边（含自身）最近的偏爱字符位置 right[i]。

对于每个非偏爱字符位置 ：

• 左侧距离 （若左边无偏爱字符则为 ）
• 右侧距离 （若右边无偏爱字符则为 ）
• 若 ，替换为左边的偏爱字符（等距时选左边）
• 否则替换为右边的偏爱字符

题目保证偏爱字符至少出现一次，所以每个位置至少有一侧能找到偏爱字符。

时间复杂度 ，空间复杂度 。

代码

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    set<char> fav;
    for(int i = 0; i < m; i++){
        char c;
        scanf(" %c", &c);
        fav.insert(c);
    }
    char s[200005];
    scanf("%s", s);

    vector<int> left(n, -1), right(n, -1);

    for(int i = 0; i < n; i++){
        if(fav.count(s[i])) left[i] = i;
        else if(i > 0) left[i] = left[i-1];
    }
    for(int i = n-1; i >= 0; i--){
        if(fav.count(s[i])) right[i] = i;
        else if(i < n-1) right[i] = right[i+1];
    }

    for(int i = 0; i < n; i++){
        if(fav.count(s[i])){
            putchar(s[i]);
        } else {
            int dl = (left[i] == -1) ? INT_MAX : i - left[i];
            int dr = (right[i] == -1) ? INT_MAX : right[i] - i;
            if(dl <= dr) putchar(s[left[i]]);
            else putchar(s[right[i]]);
        }
    }
    putchar('\n');
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Set<Character> fav = new HashSet<>();
        for (int i = 0; i < m; i++) {
            fav.add(sc.next().charAt(0));
        }
        String s = sc.next();

        int[] left = new int[n], right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);

        for (int i = 0; i < n; i++) {
            if (fav.contains(s.charAt(i))) left[i] = i;
            else if (i > 0) left[i] = left[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            if (fav.contains(s.charAt(i))) right[i] = i;
            else if (i < n - 1) right[i] = right[i + 1];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (fav.contains(s.charAt(i))) {
                sb.append(s.charAt(i));
            } else {
                int dl = (left[i] == -1) ? Integer.MAX_VALUE : i - left[i];
                int dr = (right[i] == -1) ? Integer.MAX_VALUE : right[i] - i;
                if (dl <= dr) sb.append(s.charAt(left[i]));
                else sb.append(s.charAt(right[i]));
            }
        }
        System.out.println(sb.toString());
    }
}