题解 | #偏爱的字符#

题目链接

题目描述

小李对一些字符有特殊的偏爱。对于一个给定的字符串，他会把所有非偏爱字符替换成距离它最近的偏爱字符。这里的距离指的是字符串下标之差的绝对值。如果一个非偏爱字符与两个偏爱字符的距离相等，他会选择位置更靠左（下标更小）的那个。所有替换操作是同时进行的。

思路分析

这是一个典型的字符串处理问题，核心在于为每个非偏爱字符高效地找到其“最近”的偏爱字符。

最直观的想法是，对每一个非偏爱字符，都去遍历整个字符串以找到所有偏爱字符，然后计算距离，找出最近的一个。这种方法的时间复杂度为 $O(n^2)$ ，其中 $n$ 是字符串的长度。对于本题 $n \le 10^5$ 的数据范围，该方法会超时。

我们可以发现，对于任何一个位置 $i$ ，影响其替换结果的只有它左侧最近的偏爱字符和右侧最近的偏爱字符。其他更远的偏爱字符无需考虑。

基于此，我们可以通过两次线性扫描预处理出每个位置的信息：

$left$ 数组： $left[i]$ 存储位置 $i$ 左侧（包括自身）最近的偏爱字符的下标。我们可以从左到右遍历一次字符串，用一个变量记录沿途遇到的最后一个偏爱字符的下标，即可填充该数组。
$right$ 数组： $right[i]$ 存储位置 $i$ 右侧（包括自身）最近的偏爱字符的下标。同理，我们可以从右到左遍历一次字符串来填充该数组。

完成预处理后，我们再遍历一次原字符串来构建新字符串。对于每个非偏爱字符的位置 $i$ ，我们比较它到 $left[i]$ 和 $right[i]$ 的距离：

令左侧距离为 $d_l = i - left[i]$ ，右侧距离为 $d_r = right[i] - i$ 。
如果 $d_l \le d_r$ ，则选择左侧的偏爱字符进行替换。注意，这里的 ≤ 直接处理了题目中“距离相等时选左边”的平局规则。
否则，选择右侧的。

同时需要处理边界情况，即某一边没有偏爱字符。整个算法只需要三次线性扫描。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    set<char> favored_chars;
    for (int i = 0; i < m; ++i) {
        char c;
        cin >> c;
        favored_chars.insert(c);
    }

    string s;
    cin >> s;

    vector<int> left(n, -1);
    int last_fav_idx = -1;
    for (int i = 0; i < n; ++i) {
        if (favored_chars.count(s[i])) {
            last_fav_idx = i;
        }
        left[i] = last_fav_idx;
    }

    vector<int> right(n, -1);
    last_fav_idx = -1;
    for (int i = n - 1; i >= 0; --i) {
        if (favored_chars.count(s[i])) {
            last_fav_idx = i;
        }
        right[i] = last_fav_idx;
    }

    string result = "";
    for (int i = 0; i < n; ++i) {
        if (favored_chars.count(s[i])) {
            result += s[i];
        } else {
            int l_idx = left[i];
            int r_idx = right[i];

            if (l_idx == -1) {
                result += s[r_idx];
            } else if (r_idx == -1) {
                result += s[l_idx];
            } else {
                if (i - l_idx <= r_idx - i) {
                    result += s[l_idx];
                } else {
                    result += s[r_idx];
                }
            }
        }
    }

    cout << result << endl;

    return 0;
}

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Set<Character> favoredChars = new HashSet<>();
        for (int i = 0; i < m; i++) {
            favoredChars.add(sc.next().charAt(0));
        }

        String s = sc.next();

        int[] left = new int[n];
        int lastFavIdx = -1;
        for (int i = 0; i < n; i++) {
            if (favoredChars.contains(s.charAt(i))) {
                lastFavIdx = i;
            }
            left[i] = lastFavIdx;
        }

        int[] right = new int[n];
        lastFavIdx = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (favoredChars.contains(s.charAt(i))) {
                lastFavIdx = i;
            }
            right[i] = lastFavIdx;
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (favoredChars.contains(s.charAt(i))) {
                result.append(s.charAt(i));
            } else {
                int lIdx = left[i];
                int rIdx = right[i];

                if (lIdx == -1) {
                    result.append(s.charAt(rIdx));
                } else if (rIdx == -1) {
                    result.append(s.charAt(lIdx));
                } else {
                    if (i - lIdx <= rIdx - i) {
                        result.append(s.charAt(lIdx));
                    } else {
                        result.append(s.charAt(rIdx));
                    }
                }
            }
        }
        System.out.println(result.toString());
    }
}

n, m = map(int, input().split())
favored_chars = set(input().split())
s = input()

left = [-1] * n
last_fav_idx = -1
for i in range(len(s)):
    if s[i] in favored_chars:
        last_fav_idx = i
    left[i] = last_fav_idx

right = [-1] * n
last_fav_idx = -1
for i in range(len(s) - 1, -1, -1):
    if s[i] in favored_chars:
        last_fav_idx = i
    right[i] = last_fav_idx

result = []
for i in range(len(s)):
    if s[i] in favored_chars:
        result.append(s[i])
    else:
        l_idx = left[i]
        r_idx = right[i]

        if l_idx == -1:
            result.append(s[r_idx])
        elif r_idx == -1:
            result.append(s[l_idx])
        else:
            if i - l_idx <= r_idx - i:
                result.append(s[l_idx])
            else:
                result.append(s[r_idx])

print("".join(result))

算法及复杂度

算法：预处理 + 线性扫描
时间复杂度： $O(n)$ ，其中 $n$ 是字符串的长度。算法主要包含三次独立的线性扫描。
空间复杂度： $O(n)$ ，需要额外的空间存储 $left$ 和 $right$ 两个数组。