本题要求构造一个包含所有 $26$ 个小写字母的线性排列（即一行键盘），使得给定字符串 $s$ 中每一对相邻字符在排列中也相邻。若存在这样的排列，输出任意一个；否则输出 NO。

算法思路

采用贪心策略，模拟在一条线上逐渐添加字符的过程。我们维护：

• 一个双向链表（或数组）表示当前已确定的键盘排列，初始为空。
• 一个指针 cur，指向当前字符在链表中的位置（即当前处理到的字符串字符在键盘上的位置）。

遍历字符串 $s$ 的每个字符（设当前字符为 $c$，上一个字符为 $prev$，初始时 $prev$ 不存在）：

1. 如果 $c$ 尚未出现在键盘中：
   • 尝试将 $c$ 放在 $prev$ 的左侧或右侧（即与 $prev$ 相邻的位置）。
   • 如果 $prev$ 的两侧都已被占用（即左右邻居都存在），则无法放置，输出 NO。
   • 否则，将 $c$ 放置在空闲的一侧，并更新 cur 为 $c$ 的位置。
2. 如果 $c$ 已经出现在键盘中：
   • 检查 $c$ 是否与 $prev$ 在键盘上相邻（即 $c$ 是 $prev$ 的左邻居或右邻居）。
   • 若不是，则输出 NO。
   • 若是，则更新 cur 为 $c$ 的位置。

遍历结束后，所有在 $s$ 中出现过的字符已经按相邻关系放置好。此时，将尚未出现在键盘中的字母任意附加到键盘的两端（因为未出现的字母不会破坏任何相邻条件），即可得到最终 $26$ 个字母的排列。

正确性说明

• 必要性：若存在合法排列，则对于字符串中每对相邻字符 $(s_i, s_{i+1})$，它们在排列中必须相邻。贪心算法在每一步都强制当前字符与上一个字符相邻，因此如果存在解，该构造过程不会产生矛盾。
• 充分性：若贪心过程未遇到矛盾，则构造出的部分排列已经满足所有相邻要求。添加未出现的字母不会产生新的相邻对（因为 $s$ 中未涉及它们），因此最终排列合法。

实现细节

• 可以用数组 pos[26] 记录每个字母在最终排列中的位置（或 -1 表示未放置）。
• 用数组 left[26] 和 right[26] 模拟双向链表，表示每个字母的左邻和右邻（若不存在则为 -1）。
• 维护当前字符 cur 和已放置字母的边界（最左和最右字母），方便添加新字母时判断两侧是否空闲。

复杂度

• 时间复杂度：$O(|s|)$，每个字符至多处理一次。
• 空间复杂度：$O(|\Sigma|)$，即 $O(26)$。

示例解析

以样例中的 ababa 为例：

1. 第一个字符 a，直接放置，cur = a。
2. 第二个字符 b，未出现，放在 a 右侧，cur = b。
3. 第三个字符 a，已出现，检查是否与 b 相邻（是），cur = a。
4. 第四个字符 b，已出现，检查是否与 a 相邻（是），cur = b。
5. 第五个字符 a，已出现，检查是否与 b 相邻（是），cur = a。 遍历结束，当前键盘为 a - b，将未出现字母任意添加，例如 bacdefghijklmnopqrstuvwxyz。

代码框架（C++）

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

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    // 初始化左右邻居数组，-1 表示无邻居
    int left[26], right[26];
    memset(left, -1, sizeof(left));
    memset(right, -1, sizeof(right));

    bool ok = true;
    int cur = s[0] - 'a';  // 当前字符位置

    for (int i = 1; i < n; ++i) {
        int x = s[i] - 'a';
        int prev = s[i-1] - 'a';

        if (left[x] == -1 && right[x] == -1) {
            // 新字符，尝试放在 prev 旁边
            if (left[prev] == -1) {
                left[prev] = x;
                right[x] = prev;
            } else if (right[prev] == -1) {
                right[prev] = x;
                left[x] = prev;
            } else {
                ok = false;
                break;
            }
            cur = x;
        } else {
            // 已存在，检查是否与 prev 相邻
            if (left[prev] != x && right[prev] != x) {
                ok = false;
                break;
            }
            cur = x;
        }
    }

    if (!ok) {
        cout << "NO\n";
        return;
    }

    // 构造最终排列
    string ans(26, ' ');
    int idx = 0;
    // 先找到最左端的字母（没有左邻居）
    int start = cur;
    while (left[start] != -1) start = left[start];
    // 从左到右收集所有已放置字母
    for (int i = start; i != -1; i = right[i]) {
        ans[idx++] = i + 'a';
    }
    // 添加未出现字母
    for (int i = 0; i < 26; ++i) {
        if (left[i] == -1 && right[i] == -1 && i != start) {
            ans[idx++] = i + 'a';
        }
    }

    cout << "YES\n" << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

总结

该贪心算法通过模拟“逐步扩展”的过程，高效判断是否存在合法排列并构造出一个可行解。关键在于维护每个字母的左右邻居，并保证每个新字母只能紧贴当前字母的未占用侧。