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 Generated String

Number: 3770

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two strings, str1 and str2, we need to construct a string word of length (n + m - 1) such that for every index i (0 <= i < n) the substring of length m starting at index i in word meets a constraint:

  • If str1[i] == 'T', then word[i...i+m-1] must be exactly equal to str2.
  • If str1[i] == 'F', then word[i...i+m-1] must not equal str2. Return the lexicographically smallest word that satisfies all these constraints; if none exists, return an empty string.

Key Insights

  • The output word has fixed length: n + m - 1.
  • 'T' constraints completely fix the substring at a given starting index to be equal to str2.
  • 'F' constraints require deviation from str2 in the corresponding substring.
  • Overlapping substrings impose consistency requirements.
  • A greedy approach is used: start with the smallest possible characters (i.e., 'a') and override them where constraints force a different letter.
  • For any 'F' constraint where the current assignment accidentally equals str2, we try to minimally modify one character in order to break the match without violating other constraints.

Space and Time Complexity

Time Complexity: O(n * m) in the worst case, due to scanning and possibly adjusting m characters for each of the n positions. Space Complexity: O(n + m) for storing the final word and auxiliary variables.

Solution

We approach the problem in two phases:

  1. Initialize the word with all 'a' (the lexicographically smallest letter). For every index i where str1[i]=='T', force the substring word[i...i+m-1] to equal str2, checking for consistency in overlapping positions.
  2. For each index i with str1[i]=='F', verify if the substring equals str2. If it does, modify one character minimally (by choosing the next possible letter) so that the substring no longer equals str2. If no valid adjustment is possible, return an empty string. This greedy strategy, along with careful handling of overlaps, yields the lexicographically smallest possible valid word.

Code Solutions

# Python solution with line-by-line comments
def lex_smallest_generated_string(str1, str2):
    n = len(str1)
    m = len(str2)
    word_length = n + m - 1
    # Initialize the word with 'a' to start with the lexicographically smallest option.
    word = ['a'] * word_length

    # Helper function to assign a segment of the word starting at index 'start' with string 's'
    def assign_segment(start, s):
        for j in range(len(s)):
            pos = start + j
            # If there is a conflict (already assigned a letter that is not 'a' or the same), return False.
            if word[pos] != s[j] and word[pos] != 'a':
                return False
            word[pos] = s[j]
        return True

    # First, process all 'T' constraints: force the segment to be exactly str2.
    for i in range(n):
        if str1[i] == 'T':
            if not assign_segment(i, str2):
                return ""  # Conflict encountered

    # Next, handle 'F' constraints.
    for i in range(n):
        if str1[i] == 'F':
            segment = ''.join(word[i:i+m])
            # If the segment accidentally equals str2, modify one character in a minimal way.
            if segment == str2:
                fixed = False
                for j in range(m):
                    pos = i + j
                    original_char = word[pos]
                    # Try to choose the next lexicographically larger letter.
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        if c > original_char:
                            temp = word[pos]
                            word[pos] = c
                            if ''.join(word[i:i+m]) != str2:
                                fixed = True
                                break
                            else:
                                word[pos] = temp
                    if fixed:
                        break
                if not fixed:
                    return ""
    return ''.join(word)

# Example Tests
print(lex_smallest_generated_string("TFTF", "ab"))   # Expected output: "ababa"
print(lex_smallest_generated_string("TFTF", "abc"))  # Expected output: ""
print(lex_smallest_generated_string("F", "d"))       # Expected output: "a"
← Back to All Questions