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

Difficulty: Hard

Problem Description

You are given two strings, str1 and str2, of lengths n and m, respectively. A string word of length n + m - 1 is defined to be generated by str1 and str2 if it satisfies specific conditions based on the characters in str1. Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string.

Key Insights

  • The character 'T' in str1 indicates that the substring starting from that index must match str2.
  • The character 'F' in str1 indicates that the substring starting from that index must not match str2.
  • The solution requires careful construction of the string while ensuring it remains lexicographically smallest.
  • A greedy approach can be implemented to select the smallest possible characters at each index while respecting the conditions imposed by str1.

Space and Time Complexity

Time Complexity: O(n * m)
Space Complexity: O(n + m)

Solution

To solve this problem, we will use a greedy approach combined with string manipulation. The idea is to iterate through str1 and build the resulting string word. We will maintain a character array to hold the current state of the generated string. For each index in str1, depending on whether it is 'T' or 'F', we will either match str2 or avoid it by selecting the smallest possible character that does not lead to an invalid configuration.

  1. Create an array result of size n + m - 1 initialized with placeholder characters.
  2. Iterate through str1:
    • For 'T', place str2 starting at the current index.
    • For 'F', ensure that the substring does not match str2.
  3. If at any point the conditions cannot be satisfied, return an empty string.
  4. Construct the final result string from the result array.

Code Solutions

def lexicographically_smallest_generated_string(str1, str2):
    n, m = len(str1), len(str2)
    result = [''] * (n + m - 1)

    for i in range(n):
        if str1[i] == 'T':
            # Fill in the substring with str2
            for j in range(m):
                if i + j < len(result):
                    if result[i + j] == '':
                        result[i + j] = str2[j]
                    elif result[i + j] != str2[j]:
                        return ""  # Conflict, cannot satisfy the condition
        else:  # str1[i] == 'F'
            # Ensure the substring starting at i is not str2
            for j in range(m):
                if i + j < len(result):
                    if result[i + j] == '':
                        # Fill with the smallest character other than str2[j]
                        result[i + j] = 'a' if str2[j] != 'a' else 'b'
                    elif result[i + j] == str2[j]:
                        return ""  # Conflict, cannot satisfy the condition

    # Join the result and return the final string
    return ''.join(result).rstrip('')

# Example usage
print(lexicographically_smallest_generated_string("TFTF", "ab"))  # Output: "ababa"
← Back to All Questions