Codeforces 265C No to Palindromes! 構造字典序下一合法串

題目大意

給定長度 n (≤1000) 的字符串 s，僅含前 p (≤26) 個小寫字母。s 滿足：無長度 ≥2 的回文子串。求字典序最小的、比 s 大、同樣合法的字符串，不存在輸出 NO。

核心觀察

• 無長度 2 回文 → 相鄰字符不同；
• 無長度 3 回文 → s[i] != s[i+2]；
• 更長回文必包含長度 2 或 3 回文，故僅需檢查相鄰與間隔一位。

構造策略：從右向左嘗試增大

1. 從末位開始，嘗試將字符改為更大的合法字符（不與前一、前二字符相同）；
2. 一旦某位增大成功，其後所有位填入字典序最小的合法字符（貪心：每位選最小的不與前一、前二衝突的字符）；
3. 若所有位嘗試失敗，輸出 NO。

關鍵代碼 (C++)

bool check(int pos, char c, const string& s) {
    if (pos >= 1 && s[pos-1] == c) return false;
    if (pos >= 2 && s[pos-2] == c) return false;
    return true;
}

int main() {
    int n, p; string s;
    cin >> n >> p >> s;
    for (int i = n-1; i >= 0; --i) {
        for (char c = s[i]+1; c < 'a'+p; ++c) {
            if (!check(i, c, s)) continue;
            s[i] = c;
            // 後綴貪心填最小
            for (int j = i+1; j < n; ++j) {
                for (char c2 = 'a'; c2 < 'a'+p; ++c2) {
                    if (check(j, c2, s)) { s[j] = c2; break; }
                }
            }
            cout << s << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

複雜度

O(n × p²) ≤ 1000 × 26² ≈ 6.7e5，極快。

樣例驗證