The Next Good String

In problems on strings one often has to find a string with some particular properties. The problem authors were reluctant to waste time on thinking of a name for some string so they called it good. A string is good if it doesn't have palindrome substrings longer than or equal to d.

You are given string s, consisting only of lowercase English letters. Find a good string t with length |s|, consisting of lowercase English letters, which is lexicographically larger than s. Of all such strings string t must be lexicographically minimum.

We will call a non-empty string s[a ... b] = s_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) a substring of string s = s₁s₂... s_|s|.

A non-empty string s = s₁s₂... s_n is called a palindrome if for all i from 1 to n the following fulfills: s_i = s_{n - i + 1}. In other words, palindrome read the same in both directions.

String x = x₁x₂... x_|x| is lexicographically larger than string y = y₁y₂... y_|y|, if either |x| > |y| and x₁ = y₁, x₂ = y₂, ... , x_|y| = y_|y|, or there exists such number r (r < |x|, r < |y|), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 > y_r + 1. Characters in such strings are compared like their ASCII codes.