Practice/Amazon/Leetcode 2663. Lexicographically Smallest Beautiful String

Leetcode 2663. Lexicographically Smallest Beautiful String

CodingOptional

Problem

You are given a string s consisting only of the first k lowercase English letters (from 'a' to the k-th letter). The string is called beautiful if it does not contain any palindromic substring of length 2 or greater.

A palindromic substring of length 2 means two adjacent identical characters (like "aa"). A palindromic substring of length 3 means a pattern where the first and third characters are the same (like "aba").

Your task is to find the lexicographically smallest string of the same length as s that is:

• Strictly greater than s in lexicographic order
• Beautiful (contains no palindromic substrings of length 2 or more)
• Uses only the first k letters of the alphabet

If no such string exists, return an empty string.

Requirements

1. The output string must be the same length as the input string
2. The output must be lexicographically larger than the input
3. No two adjacent characters can be identical
4. No character at position i can equal the character at position i-2 (to prevent palindromes like "aba")
5. Only use characters from 'a' to the k-th letter of the alphabet

Constraints

• 1 ≤ s.length ≤ 100
• 2 ≤ k ≤ 26
• The input string s is guaranteed to be beautiful
• All characters in s are within the first k letters

Examples

Example 1:

Input: s = "abac", k = 3 Output: "abca" Explanation: Starting from "abac", we need the next valid string. Incrementing the last character from 'c' to the next would exceed our limit, so we backtrack. We can change position 2 from 'a' to 'c' and set position 3 to 'a', giving us "abca" which has no palindromic substrings.

Example 2:

Input: s = "abc", k = 4 Output: "aca" Explanation: We try to increment from the rightmost position. Since we can't simply increment 'c' while maintaining the beautiful property with the available characters, we backtrack and find "aca" as the next valid configuration.

Example 3:

Input: s = "ab", k = 3 Output: "ac" Explanation: Simple increment of the last character from 'b' to 'c' maintains all constraints.