Lexicographically Smallest Generated String

Lexicographically Smallest Generated String - Problem

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 the following conditions for each index 0 <= i <= n - 1:

If str1[i] == 'T', the substring of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.
If str1[i] == 'F', the substring of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.

Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".

Input & Output

Example 1 — Basic T and F constraints

$ Input: str1 = "TF", str2 = "ab"

› Output: "aba"

💡 Note: Need string of length 3. At position 0, must have "ab" (T constraint). At position 1, must NOT have "ab" (F constraint). String "aba" satisfies both: substring [0,1] = "ab" ✓, substring [1,2] = "ba" ≠ "ab" ✓

Example 2 — Multiple T constraints

$ Input: str1 = "TT", str2 = "aa"

› Output: "aaa"

💡 Note: Need string of length 3. Both positions 0 and 1 require "aa". Only "aaa" works: substring [0,1] = "aa" ✓, substring [1,2] = "aa" ✓

Example 3 — Impossible constraints

$ Input: str1 = "TF", str2 = "aa"

› Output: ""

💡 Note: Need string of length 3. Position 0 requires "aa" and position 1 forbids "aa". But if characters [0,1] = "aa", then characters [1,2] must also be "aa" (overlapping). This creates contradiction, so no valid string exists.

Constraints

1 ≤ str1.length ≤ 1000
1 ≤ str2.length ≤ 26
str1 consists only of 'T' and 'F'
str2 consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

str1 defines T/F constraints, str2 is pattern to match/avoid

Process

Check each position against constraints to build valid string

Output

Return lexicographically smallest string satisfying all constraints

Key Takeaway

🎯 Key Insight: Use greedy character placement while respecting T/F pattern constraints at each position

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is using greedy character placement with constraint propagation. Build the result string character by character, always choosing the lexicographically smallest valid character. At each position, check if placing a character violates any T (must match) or F (must not match) constraints. Best approach uses greedy construction with backtracking. Time: O(26 × (n+m)²), Space: O(n+m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Generation	O(26^(n+m-1) × n × m)	O(n + m)	Generate all possible strings and check constraints
Greedy Character Placement	O(26 × (n + m)²)	O(n + m)	Build string character by character using greedy choices with constraint checking

Brute Force Generation — Algorithm Steps

Generate all possible strings of length n+m-1
For each string, check if it satisfies all T/F constraints
Return lexicographically smallest valid string

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible strings of length n+m-1

Validate

Check each string against T/F constraints

Select

Return lexicographically smallest valid string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isValid(const char* word, const char* str1, const char* str2) {
    int n = strlen(str1), m = strlen(str2);
    int wordLen = strlen(word);
    if (wordLen != n + m - 1) return 0;
    
    for (int i = 0; i < n; i++) {
        if (i + m > wordLen) return 0;
        if (str1[i] == 'T' && strncmp(word + i, str2, m) != 0) return 0;
        if (str1[i] == 'F' && strncmp(word + i, str2, m) == 0) return 0;
    }
    return 1;
}

char* generateStrings(const char* str1, const char* str2, int pos, char* current, int resultLen) {
    if (pos == resultLen) {
        if (isValid(current, str1, str2)) {
            char* result = malloc((resultLen + 1) * sizeof(char));
            strcpy(result, current);
            return result;
        }
        return NULL;
    }
    
    for (char c = 'a'; c <= 'z'; c++) {
        current[pos] = c;
        current[pos + 1] = '\0';
        char* result = generateStrings(str1, str2, pos + 1, current, resultLen);
        if (result) return result;
    }
    return NULL;
}

char* solution(char* str1, char* str2) {
    int n = strlen(str1), m = strlen(str2);
    int resultLen = n + m - 1;
    
    char* current = malloc((resultLen + 1) * sizeof(char));
    current[0] = '\0';
    
    char* result = generateStrings(str1, str2, 0, current, resultLen);
    if (!result) {
        result = malloc(1 * sizeof(char));
        result[0] = '\0';
    }
    
    free(current);
    return result;
}

int main() {
    char str1[1001], str2[1001];
    fgets(str1, sizeof(str1), stdin);
    fgets(str2, sizeof(str2), stdin);
    str1[strcspn(str1, "\n")] = 0;
    str2[strcspn(str2, "\n")] = 0;
    
    char* result = solution(str1, str2);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26^(n+m-1) × n × m)

Generate 26^(n+m-1) possible strings, each taking O(n×m) time to validate constraints

✓ Linear Growth

Space Complexity

O(n + m)

Space for storing current string candidate and input strings

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler