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 "".

Examples

Example 1

Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation:
#### The table below represents the string `"ababa"`
Index | T/F | Substring of length `m`  
---|---|---  
0 | `'T'` | "ab"  
1 | `'F'` | "ba"  
2 | `'T'` | "ab"  
3 | `'F'` | "ba"  
The strings `"ababa"` and `"ababb"` can be generated by `str1` and `str2`.
Return `"ababa"` since it is the lexicographically smaller string.

Example 2

Input: str1 = "TFTF", str2 = "abc"
Output: ""
Explanation:
No string that satisfies the conditions can be generated.

Example 3

Input: str1 = "F", str2 = "d"
Output: "a"

Constraints

• 1 <= n == str1.length <= 10^4
• 1 <= m == str2.length <= 500
• str1 consists only of 'T' or 'F'.
• str2 consists only of lowercase English characters.

Solution

Method 1 – Greedy + Backtracking with Overlap Constraints

Intuition

We need to construct the lexicographically smallest string of length n+m-1 that satisfies the overlap constraints from str1 and str2. For each position, if str1[i] == 'T', the substring must match str2; if str1[i] == 'F', it must not. We can use backtracking with pruning, always trying the smallest possible character at each position, and backtrack if a constraint is violated.

Approach

1. Let n = len(str1), m = len(str2), and L = n + m - 1.
2. For each position in the result, try the smallest possible character ('a' to 'z').
3. For each position i where i <= n-1, check:
   • If str1[i] == 'T', ensure res[i:i+m] == str2 (if enough characters are filled).
   • If str1[i] == 'F', ensure res[i:i+m] != str2 (if enough characters are filled).
4. Use backtracking to fill the string, pruning branches that violate constraints.
5. Return the first valid string found (guaranteed to be lexicographically smallest).

Code

Python

class Solution:
    def smallestString(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        L = n + m - 1
        res = [''] * L
        def backtrack(pos: int) -> bool:
            if pos == L:
                for i in range(n):
                    sub = ''.join(res[i:i+m])
                    if str1[i] == 'T' and sub != str2:
                        return False
                    if str1[i] == 'F' and sub == str2:
                        return False
                return True
            for c in map(chr, range(ord('a'), ord('z')+1)):
                res[pos] = c
                valid = True
                i = pos - m + 1
                if 0 <= i < n:
                    sub = ''.join(res[i:i+m])
                    if '' not in sub:
                        if str1[i] == 'T' and sub != str2:
                            valid = False
                        if str1[i] == 'F' and sub == str2:
                            valid = False
                if valid and backtrack(pos+1):
                    return True
            return False
        if backtrack(0):
            return ''.join(res)
        return ''

C++

class Solution {
public:
    string smallestString(string str1, string str2) {
        int n = str1.size(), m = str2.size(), L = n + m - 1;
        string res(L, 'a');
        function<bool(int)> dfs = [&](int pos) {
            if (pos == L) {
                for (int i = 0; i < n; ++i) {
                    string sub = res.substr(i, m);
                    if (str1[i] == 'T' && sub != str2) return false;
                    if (str1[i] == 'F' && sub == str2) return false;
                }
                return true;
            }
            for (char c = 'a'; c <= 'z'; ++c) {
                res[pos] = c;
                bool valid = true;
                int i = pos - m + 1;
                if (i >= 0 && i < n) {
                    string sub = res.substr(i, m);
                    if (sub.find(' ') == string::npos) {
                        if (str1[i] == 'T' && sub != str2) valid = false;
                        if (str1[i] == 'F' && sub == str2) valid = false;
                    }
                }
                if (valid && dfs(pos+1)) return true;
            }
            return false;
        };
        if (dfs(0)) return res;
        return "";
    }
};

Java

class Solution {
    public String smallestString(String str1, String str2) {
        int n = str1.length(), m = str2.length(), L = n + m - 1;
        char[] res = new char[L];
        Arrays.fill(res, 'a');
        if (dfs(0, res, str1, str2, n, m, L)) return new String(res);
        return "";
    }
    private boolean dfs(int pos, char[] res, String str1, String str2, int n, int m, int L) {
        if (pos == L) {
            for (int i = 0; i < n; ++i) {
                String sub = new String(res, i, m);
                if (str1.charAt(i) == 'T' && !sub.equals(str2)) return false;
                if (str1.charAt(i) == 'F' && sub.equals(str2)) return false;
            }
            return true;
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            res[pos] = c;
            boolean valid = true;
            int i = pos - m + 1;
            if (i >= 0 && i < n) {
                String sub = new String(res, i, m);
                if (new String(sub).indexOf('\0') == -1) {
                    if (str1.charAt(i) == 'T' && !sub.equals(str2)) valid = false;
                    if (str1.charAt(i) == 'F' && sub.equals(str2)) valid = false;
                }
            }
            if (valid && dfs(pos+1, res, str1, str2, n, m, L)) return true;
        }
        return false;
    }
}

Go

func smallestString(str1, str2 string) string {
    n, m := len(str1), len(str2)
    L := n + m - 1
    res := make([]byte, L)
    for i := range res { res[i] = 'a' }
    var dfs func(int) bool
    dfs = func(pos int) bool {
        if pos == L {
            for i := 0; i < n; i++ {
                sub := string(res[i:i+m])
                if str1[i] == 'T' && sub != str2 { return false }
                if str1[i] == 'F' && sub == str2 { return false }
            }
            return true
        }
        for c := byte('a'); c <= 'z'; c++ {
            res[pos] = c
            valid := true
            i := pos - m + 1
            if i >= 0 && i < n {
                sub := string(res[i:i+m])
                if str1[i] == 'T' && sub != str2 { valid = false }
                if str1[i] == 'F' && sub == str2 { valid = false }
            }
            if valid && dfs(pos+1) { return true }
        }
        return false
    }
    if dfs(0) { return string(res) }
    return ""
}

Rust

impl Solution {
    pub fn smallest_string(str1: String, str2: String) -> String {
        let n = str1.len();
        let m = str2.len();
        let L = n + m - 1;
        let mut res = vec![b'a'; L];
        fn dfs(pos: usize, res: &mut Vec<u8>, str1: &[u8], str2: &[u8], n: usize, m: usize, L: usize) -> bool {
            if pos == L {
                for i in 0..n {
                    let sub = &res[i..i+m];
                    if str1[i] == b'T' && sub != str2 { return false; }
                    if str1[i] == b'F' && sub == str2 { return false; }
                }
                return true;
            }
            for c in b'a'..=b'z' {
                res[pos] = c;
                let mut valid = true;
                let i = pos as isize - m as isize + 1;
                if i >= 0 && i < n as isize {
                    let sub = &res[i as usize..i as usize + m];
                    if str1[i as usize] == b'T' && sub != str2 { valid = false; }
                    if str1[i as usize] == b'F' && sub == str2 { valid = false; }
                }
                if valid && dfs(pos+1, res, str1, str2, n, m, L) { return true; }
            }
            false
        }
        if dfs(0, &mut res, str1.as_bytes(), str2.as_bytes(), n, m, L) {
            String::from_utf8(res).unwrap()
        } else {
            String::new()
        }
    }
}

TypeScript

class Solution {
    smallestString(str1: string, str2: string): string {
        const n = str1.length, m = str2.length, L = n + m - 1;
        const res = Array(L).fill('a');
        function dfs(pos: number): boolean {
            if (pos === L) {
                for (let i = 0; i < n; i++) {
                    const sub = res.slice(i, i+m).join('');
                    if (str1[i] === 'T' && sub !== str2) return false;
                    if (str1[i] === 'F' && sub === str2) return false;
                }
                return true;
            }
            for (let c = 97; c <= 122; c++) {
                res[pos] = String.fromCharCode(c);
                let valid = true;
                const i = pos - m + 1;
                if (i >= 0 && i < n) {
                    const sub = res.slice(i, i+m).join('');
                    if (str1[i] === 'T' && sub !== str2) valid = false;
                    if (str1[i] === 'F' && sub === str2) valid = false;
                }
                if (valid && dfs(pos+1)) return true;
            }
            return false;
        }
        if (dfs(0)) return res.join('');
        return '';
    }
}

Complexity

• ⏰ Time complexity: O(26^(n+m-1)) in the worst case (brute force), but pruning makes it much faster for small n, m.
• 🧺 Space complexity: O(n+m), for the result and recursion stack.