小欧的字符串构造

OPPO 笔试真题 · 2024 秋招 · 算法岗

判题请到牛客原题提交。

题目描述

小欧有一个字符串 $s$ ，她想构造一个长度为 $k$ 的字符串 $t$ ，使得 $s+t$ 或 $t+s$ 拼成的字符串是回文串。

如果可以构造，则输出 $t$ ，若无法构造，请输出 -1。

输入格式

第一行输入一个长度不超过 $10^5$ 的字符串 $s$。

第二行输入一个整数 $k(1 \leq k \leq 10^5)$ 。

输出格式

输出一个字符串表示答案。若无法构造，则输出 -1。

示例

示例 1

输入：

abc
3

输出：

cba

说明：

可以把字符串拼成abccba或cbaabc，这两个字符串都是回文串。

---

解题思路

第一步：理解问题本质

我们要造一个长度固定为 k 的 t，让 s + t 或者 t + s 成为回文串。
记 n = len(s)。关键问题是：t 到底有多少自由度？

答案是「取决于 k 和 n 的大小关系」，两种情况要分开处理。

第二步：k ≥ n 时一定有解

先记住一个基本事实：s + rev(s) 一定是回文。
设 w = s + rev(s)，长度是 2n。当 i < n 时 w[i] = s[i]；
而它的对称位置 2n-1-i >= n，落在 rev(s) 里，
w[2n-1-i] = s[2n-1-(2n-1-i)] = s[i]。两边永远相等，所以 w 是回文。

于是可以这样拼：t = u + rev(s)，其中 u 的长度是 k - n。此时

s + t = s + u + rev(s)

它的反转是 s + rev(u) + rev(s)。两式对比可知：只要 u 自己是回文，
整个串就是回文。而「长度任意的全 'a' 串」永远满足这个条件。

所以 k ≥ n 时答案一定存在，取 t = 'a' * (k - n) + rev(s)。
当 k == n 时 u 为空串，t 就是 rev(s)。

第三步：k < n 时 t 被唯一确定

这时 t 比 s 短，拼接后 t 会整个落在某一侧，t 的每一位都被对面「锁死」。

先看 s + t。这个串的前 k 个字符就是 s 的前 k 个字符，
而回文要求它们与最后 k 个字符一一镜像，末尾 k 个字符恰好是 t 倒过来。
所以 t 只能是：

t = rev(s[:k])

t 定下来之后，还要检查中间没被配对的部分。此时首尾各消耗掉 k 个字符，
剩下的 s[k:] 必须自己构成回文，否则 s + t 不是回文。

再看 t + s，同理：t 只能是 rev(s[n-k:])，并要求 s[:n-k] 是回文。

两条路都走不通，才输出 -1。

---

完整代码实现

import sys


def solve() -> None:
    """按 k 与 len(s) 的大小关系分情况构造 t"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    s = data[0].decode()
    k = int(data[1])
    n = len(s)

    if k >= n:
        # s + rev(s) 是回文，中间塞一段回文（全 'a'）不破坏对称性
        t = "a" * (k - n) + s[::-1]
    elif s[k:] == s[k:][::-1]:
        # 让 s + t 成为回文：t 由 s 的前 k 个字符镜像决定
        t = s[:k][::-1]
    elif s[:n - k] == s[:n - k][::-1]:
        # 让 t + s 成为回文：t 由 s 的后 k 个字符镜像决定
        t = s[n - k:][::-1]
    else:
        t = "-1"

    sys.stdout.write(t + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1：s = "abc"，k = 3。

k == n，走第一支：t = rev("abc") = "cba"。
检查 s + t = "abccba"，反转还是 "abccba"，是回文；t + s = "cbaabc" 也是回文。

再看 s = "ab"，k = 5（k > n）：

k - n = 3，先补 "aaa"，再接 rev("ab") = "ba"，得到 t = "aaaba"。
s + t = "abaaaba"，反转后仍是 "abaaaba"，成立。

再看 s = "aab"，k = 1（k < n）：

检查项	结果
s[k:] = s[1:] = "ab" 是否回文	否
s[:n-k] = s[:2] = "aa" 是否回文	是

于是走 t + s 这条分支：t = rev(s[2:]) = rev("b") = "b"。
验证 t + s = "baab"，是回文，成立。

再看 s = "aba"，k = 1：

s[1:] = "ba" 不是回文，s[:2] = "ab" 也不是回文，两条路都不通，输出 -1。

手工验证也确实是这个结论：两条路线都要求 t = "a"，
对应的拼接分别是 s + t = "abaa" 和 t + s = "aaba"，两者都不是回文。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
分类构造	O(n + k)	O(n + k)	只需几次切片与回文比较，推荐
枚举所有 t	O(26^k)	O(k)	不可行，k 可达 10^5

---

易错点总结

1. k 比 n 大时直接输出 rev(s)

rev(s) 的长度是 n，而题目要求 t 的长度恰好是 k。
必须把多出来的 k - n 个字符补在 rev(s) 前面，且补的那一段自身要是回文。

2. 两条分支的切片搞反

• s + t 对应 t = rev(s[:k]) —— 用 s 的前 k 个字符；
• t + s 对应 t = rev(s[n-k:]) —— 用 s 的后 k 个字符。

写反了长度虽然一样，但拼出来的串不是回文。

3. 回文检查和错误的串比

要检查的是剩下的那一段（s[k:] 或 s[:n-k]），不是整个 s。

4. 忘记空串也是回文

当 k == n 时 s[k:] 是空串，空串按定义是回文。
代码里 k >= n 的分支已经先处理了这种情况，逻辑是一致的。

---

扩展思考

• 如果要求输出字典序最小的合法 t，k ≥ n 的补位段要全部填 'a'（本解已满足），
  k < n 时两条分支都可行则取字典序更小的那个。
• 如果要求 s + t 和 t + s 同时是回文，就不能只照顾一侧，
  需要同时满足两套镜像条件，可选的 t 会少很多。
• 「s + rev(s) 一定是回文」是构造题的常用零件，
  遇到「补一段让整体回文」的问题都可以先想到它。

---

相关题目

• 小欧的red填充