【cf464A】No to Palindromes!

2014年9月8日1,5053

Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and sdoesn’t contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input

The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting ofn small English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print “NO” (without the quotes).

Sample test(s)
input

output

input

output

input

output

Note

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s1 = t1, …, si = ti, si + 1 > ti + 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.

 

题解

题意是就是找一个字典序大于s且最小的串,每个字母在p的范围内,串的任意部分都不能是回文

按照KuribohG的做法。。。(由于我很逗写了不知道什么傻逼玩意)

串的任意部分都不能是回文=串中任意连续3个字符互不相同

而要求字典序最小,应该保持前面的尽量多字符是不改动的

那么只要从后往前枚举每一位,如果某一位a[x]改为k(k>a[x])后与a[x-1],a[x-2]都不同,那么a[1]~a[x-1]就可以确定了

再从x+1开始贪心

举个例子

5 4

abdcb

发现将第二位改成c后与前面的俩位不同,即可以确定ac为开头,可以证明一定能得到解,剩下的几位贪心即可

acbac为最优解

 

  • 欧阳茹芯2014年9月8日 下午4:03 回复

    没懂

    #1  
    • hzwer2014年9月8日 下午4:37 回复
      admin

      一定是我逗了。。。我重新写了。。。

      #11
  • 欧阳茹芯2014年9月8日 下午4:05 回复

    懂了,谢谢。。。。。。。。。。。。。。。。。

    #2