No to Palindromes：字典序下一個無回文子串字符串構造

題目大意

給定長度 n、字符集大小 p（前 p 個小寫字母）、一個合法字符串（無長度≥2 的回文子串）。求字典序下一個合法字符串，不存在輸出 "NO"。

核心觀察

• 合法條件：任意相鄰兩字符不同，任意間隔一個字符不同（即 s[i] != s[i-1] 且 s[i] != s[i-2]）
• 字典序下一個 = 從右向左找第一個可增的位置，增至最小合法字符，後綴填最小合法字符

算法流程

1. 從右向左遍歷位置 i
2. 嘗試將 s[i] 增加到 'a'+p-1 範圍內的最小合法字符（不等於左側 1、2 位）
3. 若找到，從 i+1 到末尾，每位填最小合法字符（不等於左側 1、2 位）
4. 若全遍歷無解，輸出 "NO"

代碼實現

#include <cstdio>
#include <cstring>
using namespace std;

char a[1234567];
int n, p;

// 嘗試在位置 now 增加字符，成功返回 true
bool judge(int now) {
    for (int i = 1; ; ++i) {
        if (a[now] + i > 'a' + p - 1) return false;
        if (now > 0 && a[now] + i == a[now-1]) continue;
        if (now > 1 && a[now] + i == a[now-2]) continue;
        a[now] += i;
        return true;
    }
}

// 位置 now 填最小合法字符
void get_min(int now) {
    for (int i = 0; ; ++i) {
        if (now > 0 && 'a' + i == a[now-1]) continue;
        if (now > 1 && 'a' + i == a[now-2]) continue;
        a[now] = 'a' + i;
        return;
    }
}

int main() {
    scanf("%d%d", &n, &p);
    scanf("%s", a);
    int ok = 0, pos = -1;
    for (int i = n-1; i >= 0; --i) {
        if (judge(i)) { ok = 1; pos = i; break; }
    }
    if (ok) {
        for (int i = pos+1; i < n; ++i) get_min(i);
        printf("%s\n", a);
    } else {
        printf("NO\n");
    }
    return 0;
}

關鍵點

• 回文條件簡化：只需檢查長度 2 和 3 的回文，更長回文必包含短回文
• 貪心填充後綴：每位選最小合法字符，保證字典序最小
• 從右向左修改：盡量改動低位，讓前綴保持不變，獲得字典序剛好下一個

複雜度

• 時間：O(n × p)，p ≤ 26，實際極快
• 空間：O(n)

此題屬於「字典序下一個合法序列」經典模板，關鍵在於合法性判斷的局部性（只依賴左側常數位置）。