Carl and Acceptable Strings

Carl loves solving word puzzles. He is solving a complicated word puzzle and gets stuck at some point and asks you

for your help.

The puzzle has a set of rules for a string to be considered acceptable. A string is considered acceptable if each of its

characters is one of the first $K$ letters of the English alphabet, and none of its substrings is a palindrome $($of length $2$ or

more$)$

For example, the string "abcde" is considered acceptable for $k=5$ but not for $k=4($Because $\text{'}$e$\text{'}$ is the $5$ th letter of the

English alphabet$).$ The string "aabc" is not acceptable because of the presence of $"$aa$",$ which is a palindrome.

You are given an acceptable string $s$ having only lowercase English alphabets. Your task is to return the next

lexicographically greater acceptable string that has the same length as the input string or return $\text{'}$NO$\text{'}$ if such a string

does not exist.

Note: A string $r$ is considered lexicographically greater than string $s$ of the same length, if there exists a number $/$

such that $r_1=s_1,r_2=s_2,$dots,$r_1=s_i,r_{i+1}>s_{i+1}$

Input Specification:

input$1$: an integer denoting $K$

input$2$: an input string $s$

Output Specification:

The next lexicographically greater acceptable string of the same length. Note: A string $r$ is considered lexicographically greater than string $s$ of the same length, if there exists a number i$,$

such that $f_1=s_1,r_2=s_2,f_1=s_1,r_{101}>s_n+1$

Input Specification:

input$1$: an integer denoting $K$

input$2$: an input string $S$

Output Specification:

The next lexicographically greater acceptable string of the same length.

Example $1$:

input$1$: $5$

input$2$: acbdac

Output: acbdae

Explanation:

The String "acbdae" is acceptable strings for $k=5$ as the letters it contains are among the first $5$ letters of the Englost

aiphabet and none of their substrings are palindromes. So$,$ "acbdae" will be returned as the answer.

Example $2$:

input$1$: $3$

input$2$: cba

Output: NO

Explanation:

There are no acceptable strings of length $3$ for $k=3$ that are lexicographically greater than cba whose substrings a

not palindromes

Provide the java solution with $0($n$)$ complexity