Get Special String

Developers at Amazon are working on a text generation utility for one of their new products.

Currently, the utility generates only special strings. A string is considered special if there are no matching adjacent characters. Given a string s of length n, the task is to generate a special string of length n that is lexicographically greater than s. If multiple such special strings are possible, the lexicographically smallest one should be returned.

Key Concepts:

1. Special String: A string is special if no two adjacent characters are the same.
2. Lexicographical Order: This is a generalization of the way words are ordered in dictionaries. For example:
   • "abc" is lexicographically smaller than "abd" because 'c' comes before 'd' in the alphabet.
   • A string a is lexicographically smaller than b if:
     • a is a prefix of b, but not equal to b.
     • In the first position where a and b differ, the character in a comes before the character in b.
3. Character Restrictions:
   • If the character is 'z', it is the last character in the alphabet and cannot be increased further.
   • The string should not wrap around to 'a' after 'z'.
   • The output string must not have any adjacent characters that are the same.

Function Description

Complete the function getSpecialString in the editor below.

Function Signature:

def getSpecialString(s: str) -> str:
    pass

Input:

• s: A string of length n (1 ≤ |s| ≤ 10^6), consisting of lowercase English letters only.

Output:

• Returns the lexicographically smallest string that is greater than s and special. If no such special string exists, return "-1".

---

Example 1:

Input:

s = "abbd"

Output:

"abca"

Explanation: Some of the special strings that are lexicographically greater than s are shown. The lexicographically smallest special string that is greater than "abbd" is "abca".

Example 2:

Input:

s = "abccde"

Output:

"abcdab"

Explanation: Some of the special strings that are lexicographically greater than s are "abcdde", "abcdab", "abcdbc". The lexicographically smallest special string that is greater than "abccde" is "abcdab".

Example 3:

Input:

s = "zzab"

Output:

"-1"

Explanation: There is no special string of length 4 that is lexicographically greater than "zzab".

---

Constraints:

• 1 ≤ |s| ≤ 10^6
• s consists of lowercase English letters only.

---

需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.