We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest Beautiful String

Number: 2687

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given a string s of length n that is already beautiful (it only contains the first k letters of the English lowercase alphabet and has no palindromic substring of length ≥ 2) along with an integer k, return the lexicographically smallest beautiful string of length n which is strictly larger than s. If no such string exists, return an empty string.

A string is beautiful if:

  • It consists only of the first k letters (from 'a' to the k-th letter).
  • It does not contain any substring (of length 2 or more) that is a palindrome. In practice, this means that no two adjacent characters can be equal (avoiding palindromic substrings of length 2) and any pattern x ? x (for length 3) is forbidden.

Key Insights

  • We need to find the next lexicographically greater string than s while maintaining the beauty constraint.
  • The beauty constraint can be enforced by ensuring that:
    • For any position i, result[i] ≠ result[i-1] (avoids palindromic substrings of length 2).
    • For any position i ≥ 2, result[i] ≠ result[i-2] (avoids palindromic substrings of length 3).
  • We use a backtracking/greedy approach:
    • Traverse s from right to left and try to increment the character at a given position.
    • Once a valid increment is found, fill the positions to the right with the smallest valid characters.
  • At each step, only characters from 'a' to ('a' + k - 1) are allowed.

Space and Time Complexity

Time Complexity: O(n * k) in the worst case, where n is the length of the string and k is the number of valid letters. Space Complexity: O(n), needed for storing the result string.

Solution

We approach the problem by iterating from the end of the given string s. For each index, try to replace the current character with the next available character (smaller than the maximum allowed letter) that still keeps the string beautiful up to that point. Once a replacement is made, greedily fill the rest of the positions with the smallest valid character that maintains the beauty constraints. If no valid replacement can be found at any position, return an empty string.

The main data structure used is a mutable character list for easy modifications. The algorithm ensures that at every position, the two constraints (adjacent and one-gap) are checked to maintain a “beautiful” string. This backtracking (or reverse greedy) technique ensures that we find the smallest lexicographic string strictly greater than s.

Code Solutions

# Python solution with detailed comments.
class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        # Convert string to list for easier manipulation
        s_list = list(s)
        # Allowed characters list (only first k letters)
        allowed = [chr(ord('a') + i) for i in range(k)]
        
        # Helper function to check if placing a char at pos is valid.
        def valid(res, pos, ch):
            # Check left neighbor to avoid palindrome of length 2.
            if pos >= 1 and res[pos - 1] == ch:
                return False
            # Check neighbor two positions to avoid x ? x pattern.
            if pos >= 2 and res[pos - 2] == ch:
                return False
            return True

        # Try to increment the string by working backwards.
        for i in range(n - 1, -1, -1):
            # Try to find a valid character greater than the current letter at s_list[i].
            for next_char in allowed[allowed.index(s_list[i]) + 1:]:
                if valid(s_list, i, next_char):
                    # Set current position to this valid character.
                    s_list[i] = next_char
                    # Fill positions after i with the smallest valid letter.
                    for j in range(i + 1, n):
                        for candidate in allowed:
                            if valid(s_list, j, candidate):
                                s_list[j] = candidate
                                break
                        else:
                            # If no candidate is found, break out and try a different increment.
                            break
                    else:
                        # If successful in filling entire list, return the result.
                        return "".join(s_list)
            # If no valid replacement is found, continue to previous index.
        # If no solution exists, return an empty string.
        return ""
        
# Example usage:
# sol = Solution()
# print(sol.smallestBeautifulString("abcz", 26))  # Expected output: "abda"
← Back to All Questions