Codeforces Round #265 (Div. 2) C. No to Palindromes!

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s₁?=?t₁, ..., s_i?=?t_i, s_i?+?1?>?t_i?+?1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

题意：求满足大于给定串的序列，而且两个序列都不包含长度大于等于2的回文子串

思路：首先，因为不能有长度大于等于2的子串，所以当前位置是不能和它的前一个和前第二个一样的。因为给定串也是不包含回文子串的，所以为了能找个一个最小的满足条件的字符串，我们从右往前改，找到一个满足不与前两个一样的位置的话，那么从这个位置往右就是填写不构成回文的最小串了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;

int n, p;
char str[maxn], tmp;

int find(const int &x) {
	if (x == -1) 
		return 0;
	for (int i = 1; ; i++) {
		if (str[x] + i >= tmp) break;
		if (x > 0 && str[x-1] == str[x] + i) continue;
		if (x > 0 && str[x-2] == str[x] + i) continue;
		str[x] += i;
		return 1;
	}

	if (!find(x-1)) 
		return 0;

	str[x] = 'a';
	for (int i = 0; ; i++) {
		if (str[x] + i >= tmp) break;
		if (x > 0 && str[x-1] == str[x] + i) continue;
		if (x > 1 && str[x-2] == str[x] + i) continue;
		str[x] += i;
		return 1;
	}
	return 0;
}

int main() {
	scanf("%d%d", &n, &p);	
	tmp = 'a' + p;
	scanf("%s", str);
	if (find(n-1))
		printf("%s\n", str);
	else printf("NO\n");
	return 0;
}