0

Special String

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
75%

Problem Statement
Suggest Edit

A string S is said to be special if each of its character is one of the first P letters of the English alphabet and S doesn't contain any palindrome contiguous substring of length 2 or more.

Given a special string S of length N, find the lexicographically next special string of the same length or else state that such string does not exist. Print the output string if it exists, otherwise, print "NO" (without quotes).

Note:
It is guaranteed that the input string is special.
Input format :
Line 1 : Two integers, N and P (separated by space)
Line 2 : String S
Output format :
Next special string or "NO"
Constraints :
1 <= N <= 1000
1 <= P <= 26

String S contains only lowercase letters i.e [a-z]
Sample Input 1 :
3 3
cba
Sample Output 1 :
NO
Sample Input 2 :
3 4
cba
Sample Output 2 :
cbd
Sample Input 3 :
4 4
abcd
Sample Output 3 :
abda
Want to solve this problem? Login now to get access to solve the problems