2026 华为OD机试真题8月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定一个仅由小写英文字母组成的字符串 s，请判断它是否可以在删除一个字符之后，变成一个回文串。

回文串的定义是：从左到右读和从右到左读完全相同。

如果可以，输出一个数组，数组由可删除字符的索引值构成；否则输出一个空数组。

2026 华为OD机试真题8月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

输入一个字符串 s，2 ≤ s.length ≤ 10^5

输出描述

输出一个数组，内容为：N 种删除方法的字符索引值。如输入为：abca，则输出为：[1,2]，代表可以有两种删除方式：[aba, aca]。

• 1：删除索引值为 1 的字符，即删除字符 b，则变为：aca，属于回文
• 2：删除索引值为 2 的字符，即删除字符 c，则变为：aba，属于回文

示例1

输入

abca

输出

[1,2]

说明

删除 b 或删除 c 后，都可以变成回文串。

示例2

输入

abcd

输出

[]

说明

无论删除哪个字符，都无法变成回文串。

解题思路

核心思想

删除某个位置 i 后，剩余字符串是否回文，可以转化为“删除后的字符串”和“它的反串”是否完全一致。

由于需要枚举每个删除位置，但字符串长度可达 10^5，不能逐个暴力比较。可以对原串和反串分别建立双哈希，之后每次删除都用前后两段拼接的哈希在 O(1) 时间判断。

算法步骤

1. 设原串为 s，反串为 rev。
2. 分别为 s 和 rev 建立双滚动哈希前缀和幂数组。
3. 枚举删除位置 i：
   • 删除后的串等于 s[0..i-1] + s[i+1..n-1]
   • 其反串等于 rev[0..n-2-i] + rev[n-i..n-1]
4. 用哈希比较这两段拼接串是否相等。
5. 所有满足条件的 i 按升序加入答案数组。

复杂度分析

设字符串长度为 n。

• 预处理哈希：O(n)
• 枚举所有删除位置：O(n)
• 总时间复杂度：O(n)
• 额外空间复杂度：`O