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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest Beautiful String

Difficulty: Hard

Problem Description

A string is beautiful if:

  • It consists of the first k letters of the English lowercase alphabet.
  • It does not contain any substring of length 2 or more which is a palindrome.

You are given a beautiful string s of length n and a positive integer k.

Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, return an empty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

Key Insights

  • The string must consist only of the first k letters of the alphabet.
  • To ensure that the string does not contain palindromic substrings of length 2 or more, we need to avoid consecutive identical characters.
  • We can use a greedy approach to construct the next lexicographical string by iterating from the end of the string s backward.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves creating a new string that is a modified version of the input string s. We will iterate backward from the last character of s, looking for the first character that can be incremented while ensuring the new character does not lead to a palindrome.

The algorithm works as follows:

  1. Start from the end of the string and attempt to increment the character.
  2. If incrementing causes a palindrome, try to replace it with the next valid character that does not create a palindrome.
  3. If the character cannot be incremented or replaced without violating the conditions, continue moving left.
  4. If we reach the start of the string and cannot find a valid solution, return an empty string.

Code Solutions

def lexicographically_smallest_beautiful_string(s, k):
    n = len(s)
    s = list(s)
    
    # Helper function to check if the string is beautiful
    def is_beautiful(st):
        for i in range(1, len(st)):
            if st[i] == st[i - 1]:  # Check for consecutive identical characters
                return False
        return True
    
    # Start from the end and try to create the next beautiful string
    for i in range(n - 1, -1, -1):
        for c in range(ord(s[i]) + 1, ord('a') + k):
            s[i] = chr(c)  # Increment the character
            if is_beautiful(s):
                return ''.join(s[:i + 1]) + 'a' * (n - i - 1)  # Fill the rest with 'a'
            s[i] = chr(ord(s[i]) - 1)  # Restore the original character
    return ''
← Back to All Questions