小欧的字符串构造

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

思路

给定字符串 $s$ 和整数 $k$ ，构造一个长度为 $k$ 的字符串 $t$ ，使得 $s+t$ 或 $t+s$ 是回文串。若无法构造则输出 $-1$ 。

分情况讨论

情况一： $k \geq n$ （ $n$ 为 $s$ 的长度）

此时一定可以构造。令 $t$ 的后 $n$ 个字符为 $s$ 的反转，前 $k - n$ 个字符任意填充（如全填 a）。

以 $s + t$ 为例，拼接结果为 $s + \underbrace{aa\cdots a}_{k-n} + \text{reverse}(s)$ ，中间的填充字符关于自身对称，两侧的 $s$ 和 $\text{reverse}(s)$ 也对称，因此整体是回文串。

情况二： $k < n$

拼接后总长为 $n + k$ ，其中 $t$ 只覆盖一端的 $k$ 个位置。要使整体回文， $t$ 必须与 $s$ 的对应端互为反转，而 $s$ 中未被 $t$ 覆盖的中间部分必须自身是回文。

具体地，有两种子情况：

$s + t$ 回文： $t$ 必须等于 $s$ 前 $k$ 个字符的反转（即 $t = \text{reverse}(s[0..k-1])$ ），同时要求 $s[k..n-1]$ 是回文串。
$t + s$ 回文： $t$ 必须等于 $s$ 后 $k$ 个字符的反转（即 $t = \text{reverse}(s[n-k..n-1])$ ），同时要求 $s[0..n-k-1]$ 是回文串。

两种都不满足时输出 $-1$ 。

样例演示

输入 $s =$ abc， $k = 3$ ：

$k = n = 3$ ，属于情况一。
$t = \text{reverse}(\texttt{abc}) = \texttt{cba}$ 。
$s + t = \texttt{abccba}$ ，是回文串。

复杂度分析

时间复杂度： $O(n + k)$ ，回文判断和字符串构造各为线性。
空间复杂度： $O(n + k)$ ，存储结果字符串。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(const string& s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    int k;
    cin >> s >> k;
    int n = s.size();

    if (k >= n) {
        string t(k - n, 'a');
        for (int i = n - 1; i >= 0; i--) t += s[i];
        cout << t << endl;
    } else {
        // Case 1: s + t palindrome
        if (isPalindrome(s, k, n - 1)) {
            string t = "";
            for (int i = k - 1; i >= 0; i--) t += s[i];
            cout << t << endl;
        }
        // Case 2: t + s palindrome
        else if (isPalindrome(s, 0, n - k - 1)) {
            string t = "";
            for (int i = n - 1; i >= n - k; i--) t += s[i];
            cout << t << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++; r--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        int n = s.length();

        if (k >= n) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < k - n; i++) sb.append('a');
            for (int i = n - 1; i >= 0; i--) sb.append(s.charAt(i));
            System.out.println(sb.toString());
        } else {
            if (isPalindrome(s, k, n - 1)) {
                StringBuilder sb = new StringBuilder();
                for (int i = k - 1; i >= 0; i--) sb.append(s.charAt(i));
                System.out.println(sb.toString());
            } else if (isPalindrome(s, 0, n - k - 1)) {
                StringBuilder sb = new StringBuilder();
                for (int i = n - 1; i >= n - k; i--) sb.append(s.charAt(i));
                System.out.println(sb.toString());
            } else {
                System.out.println(-1);
            }
        }
    }
}

s = input()
k = int(input())
n = len(s)

def is_palindrome(s, l, r):
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True

if k >= n:
    print('a' * (k - n) + s[::-1])
else:
    if is_palindrome(s, k, n - 1):
        print(s[:k][::-1])
    elif is_palindrome(s, 0, n - k - 1):
        print(s[n-k:][::-1])
    else:
        print(-1)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => {
    lines.push(line.trim());
    if (lines.length === 2) {
        const s = lines[0];
        const k = parseInt(lines[1]);
        const n = s.length;

        function isPalindrome(s, l, r) {
            while (l < r) {
                if (s[l] !== s[r]) return false;
                l++; r--;
            }
            return true;
        }

        if (k >= n) {
            console.log('a'.repeat(k - n) + s.split('').reverse().join(''));
        } else {
            if (isPalindrome(s, k, n - 1)) {
                console.log(s.slice(0, k).split('').reverse().join(''));
            } else if (isPalindrome(s, 0, n - k - 1)) {
                console.log(s.slice(n - k).split('').reverse().join(''));
            } else {
                console.log(-1);
            }
        }
        rl.close();
    }
});