Next Greater Perfect String
Updated
Problem statement
A perfect string is a string where no two letters next to each other are the same. For example, "aba" is perfect, but "abb" is not.
You are given a string s of lowercase English letters. It may or may not be perfect.
Return the smallest perfect string, in dictionary order, that has the same length as s and comes after s. If there is no such string, return "-1".
For example, let s = "abb". The next string of length 3 is "abc", and it is perfect. The answer is "abc".
Function
nextGreaterPerfectString(s: String) → String
Complete the function nextGreaterPerfectString in the editor.
nextGreaterPerfectString has the following parameter:
String s: the starting string
Returns
String: the next perfect string, or "-1" if there is none
Examples
Example 1
s = "abzzzcd"return = "acababa""abzzzcd" is not perfect, because it has "zz". Counting from 0, positions 2 and 3 are both 'z', so the answer must differ from s at position 3 or earlier. The first letter that changes must go up. Positions 2 and 3 hold 'z', which cannot go up. So raise position 1 from 'b' to 'c', which differs from the 'a' before it. Then fill the rest with the smallest letters that keep neighbours different: "ababa". The answer is "acababa".
Example 2
s = "zzab"return = "-1"The first two letters are "zz", so the answer must differ from s in one of them. The first letter that changes must go up, but both are 'z'. So no perfect string of length 4 comes after "zzab". The answer is "-1".
Constraints
1 <= s.length <= 10^5shas only lowercase English letters ('a'to'z')
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Longest Repeated Letter Block with Adjacent SwapsIntuit · OAIntuit interview questions
- Binary CircuitAkuna Capital · OAAkuna Capital interview questions
- Minimize Expression with ParenthesesPinterest · OAPinterest interview questions
- Word Wrap with Even JustificationSentry · OA · PHONE SCREENSentry interview questions
- Palindromic StringsNVIDIA · OANVIDIA interview questions
- Get Patch SequenceMorgan Stanley · OAMorgan Stanley interview questions
- Max Number of OperationsSalesforce · OASalesforce interview questions
- Viral Content BalancerTikTok · OATikTok interview questions
- Good Binary StringsBNP Paribas · OA