Polo and Palin
All submissions for this problem are available.
Chef Palin, as his name suggests, is always very interested in palindromic strings. Recently, he made some interesting discoveries on palindromes. Chef Polo, Palin's friend, likes lucky strings a lot.
A string S is said to be K-lucky if
it does not have a non-empty palindromic substring of length more than or equal to K
For example : string zzyaabb is 3-lucky but not 2-lucky because it has palindromic substring of length 2 (like zz) while it does not have such substring of length 3.
Now Chef Polo has a string S of length N,he asks his friend Palin to find a non-empty K-lucky string P which is lexicographically larger than S and have size equal to S i.e |S|=|P|. If there are more than one such strings then he selects the string which is lexicographically smallest.
But Chef palin is busy and he knows your extra-ordinary programming skills so he wants your help
Note: Given string S may or may not be K-lucky But string P must be K-lucky
First line contain an integer K. Next line contain string S
single line contains string P. if no such string exists output "NO RESULT" (quotes for clarity).
- 1 ≤ N ≤ 4*10^5
- 1 ≤ K ≤ N
- The string consists of lowercase English alphabets.
Input: 3 zzyzzzz Output: NO RESULT
Input: 2 aba Output: abc
Input: 3 zzxzzzz Output: zzyaabb
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.