方法思路

1. 问题分析：
   • 对于字符串中的每个非偏爱字符，需要找到距离最近的偏爱字符进行替换
   • 如果有多个距离相同的偏爱字符，选择最左边的一个
   • 所有替换操作是同时进行的
2. 解决方案：
   • 首先标记所有偏爱字符在原字符串中的位置
   • 对于每个非偏爱字符，计算它与每个偏爱字符的距离，选择距离最小的
   • 如果有多个距离相同的，选择下标最小的那个偏爱字符
3. 优化方法：
   • 预处理：计算每个位置左侧最近的偏爱字符和右侧最近的偏爱字符
   • 对于每个位置i，比较左侧最近偏爱字符和右侧最近偏爱字符的距离
   • 选择距离较小的那个（如果距离相同，选择左侧的）

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        
        boolean[] isFavorite = new boolean[26]; // 使用数组而不是HashSet，更高效
        String[] favorites = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            char c = favorites[i].charAt(0);
            isFavorite[c - 'A'] = true;
        }
        
        String s = br.readLine();
        char[] result = s.toCharArray();
        
        // 预处理：计算每个位置左侧最近的偏爱字符及其距离
        int[] leftNearest = new int[n];
        char[] leftChar = new char[n];
        Arrays.fill(leftNearest, Integer.MAX_VALUE);
        
        for (int i = 0; i < n; i++) {
            char currentChar = s.charAt(i);
            if (isFavorite[currentChar - 'A']) {
                leftNearest[i] = 0;
                leftChar[i] = currentChar;
            } else if (i > 0 && leftNearest[i-1] != Integer.MAX_VALUE) {
                leftNearest[i] = leftNearest[i-1] + 1;
                leftChar[i] = leftChar[i-1];
            }
        }
        
        // 预处理：计算每个位置右侧最近的偏爱字符及其距离
        int[] rightNearest = new int[n];
        char[] rightChar = new char[n];
        Arrays.fill(rightNearest, Integer.MAX_VALUE);
        
        for (int i = n-1; i >= 0; i--) {
            char currentChar = s.charAt(i);
            if (isFavorite[currentChar - 'A']) {
                rightNearest[i] = 0;
                rightChar[i] = currentChar;
            } else if (i < n-1 && rightNearest[i+1] != Integer.MAX_VALUE) {
                rightNearest[i] = rightNearest[i+1] + 1;
                rightChar[i] = rightChar[i+1];
            }
        }
        
        // 对每个非偏爱字符，选择距离最近的偏爱字符进行替换
        for (int i = 0; i < n; i++) {
            if (!isFavorite[s.charAt(i) - 'A']) {
                // 如果左侧距离更小，或者距离相同但左侧字符更左
                if (leftNearest[i] <= rightNearest[i] && leftNearest[i] != Integer.MAX_VALUE) {
                    result[i] = leftChar[i];
                } else {
                    result[i] = rightChar[i];
                }
            }
        }
        
        System.out.println(new String(result));
    }
}

Python

def replace_characters(n, m, favorite_chars, s):
    # 将字符串转换为列表，方便修改
    result = list(s)
    
    # 预处理：计算每个位置左侧最近的偏爱字符及其距离
    left_nearest = [float('inf')] * n  # 距离
    left_char = [''] * n  # 对应的字符
    
    for i in range(n):
        if s[i] in favorite_chars:
            left_nearest[i] = 0
            left_char[i] = s[i]
        elif i > 0:
            left_nearest[i] = left_nearest[i-1] + 1
            left_char[i] = left_char[i-1]
    
    # 预处理：计算每个位置右侧最近的偏爱字符及其距离
    right_nearest = [float('inf')] * n  # 距离
    right_char = [''] * n  # 对应的字符
    
    for i in range(n-1, -1, -1):
        if s[i] in favorite_chars:
            right_nearest[i] = 0
            right_char[i] = s[i]
        elif i < n-1:
            right_nearest[i] = right_nearest[i+1] + 1
            right_char[i] = right_char[i+1]
    
    # 对每个非偏爱字符，选择距离最近的偏爱字符进行替换
    for i in range(n):
        if s[i] not in favorite_chars:
            # 如果左侧距离更小，或者距离相同但左侧字符更左
            if left_nearest[i] <= right_nearest[i] and left_char[i] != '':
                result[i] = left_char[i]
            else:
                result[i] = right_char[i]
    
    return ''.join(result)

# 读取输入
n, m = map(int, input().split())
favorite_chars = input().split()
s = input()

# 计算并输出结果
print(replace_characters(n, m, favorite_chars, s))

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <climits>
using namespace std;

string replaceCharacters(int n, const unordered_set<char>& favoriteChars, const string& s) {
    string result = s;
    
    // 预处理：计算每个位置左侧最近的偏爱字符及其距离
    vector<int> leftNearest(n, INT_MAX);
    vector<char> leftChar(n);
    
    for (int i = 0; i < n; i++) {
        if (favoriteChars.count(s[i])) {
            leftNearest[i] = 0;
            leftChar[i] = s[i];
        } else if (i > 0 && leftNearest[i-1] != INT_MAX) {
            leftNearest[i] = leftNearest[i-1] + 1;
            leftChar[i] = leftChar[i-1];
        }
    }
    
    // 预处理：计算每个位置右侧最近的偏爱字符及其距离
    vector<int> rightNearest(n, INT_MAX);
    vector<char> rightChar(n);
    
    for (int i = n-1; i >= 0; i--) {
        if (favoriteChars.count(s[i])) {
            rightNearest[i] = 0;
            rightChar[i] = s[i];
        } else if (i < n-1 && rightNearest[i+1] != INT_MAX) {
            rightNearest[i] = rightNearest[i+1] + 1;
            rightChar[i] = rightChar[i+1];
        }
    }
    
    // 对每个非偏爱字符，选择距离最近的偏爱字符进行替换
    for (int i = 0; i < n; i++) {
        if (!favoriteChars.count(s[i])) {
            // 如果左侧距离更小，或者距离相同但左侧字符更左
            if (leftNearest[i] <= rightNearest[i] && leftNearest[i] != INT_MAX) {
                result[i] = leftChar[i];
            } else {
                result[i] = rightChar[i];
            }
        }
    }
    
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    unordered_set<char> favoriteChars;
    for (int i = 0; i < m; i++) {
        char c;
        cin >> c;
        favoriteChars.insert(c);
    }
    
    string s;
    cin >> s;
    
    cout << replaceCharacters(n, favoriteChars, s) << endl;
    
    return 0;
}