3474. Lexicographically Smallest Generated String

HardGreedyStringString Matching

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

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 said to be generated by str1 and str2 if it satisfies the following conditions for every index 0 <= i <= n - 1:

If str1[i] == 'T', then the substring of word of length m starting at index i must be equal to str2. In other words, word[i..(i + m - 1)] == str2.
If str1[i] == 'F', then the substring of word of length m starting at index i must not be equal to str2. In other words, word[i..(i + m - 1)] != str2.

Your task is to return the lexicographically smallest possible string that can be generated by str1 and str2. If no valid string can be generated, return an empty string "".

In short, the string str1 acts as a sequence of constraints: each 'T' forces a specific window of word to match str2 exactly, while each 'F' forbids the corresponding window from matching str2. Among all strings word that satisfy all of these constraints simultaneously, you must find the one that is smallest in lexicographic order.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Trie / String Matching / Rolling Hash?

This problem maps to Trie / String Matching / Rolling Hash through a short path in the full flowchart.

The problem involves matching a pattern string str2 against overlapping windows in the generated word, with forced match/mismatch constraints.

Open in Flowchart

Intuition

The key observation is that the two types of constraints have very different natures, and we should handle them in a way that keeps the result as small as possible.

First, let's think about what makes a string lexicographically small. Since 'a' is the smallest character, our ideal goal is to fill word with as many 'a's as possible. So we start by assuming every position is 'a', and only change a position when a constraint forces us to.

Now consider the 'T' constraints. These are hard requirements: whenever str1[i] == 'T', the window word[i..(i + m - 1)] is completely determined—it must equal t. There is no freedom here. So we go through all the 'T' positions and stamp t onto the corresponding windows of word. We also mark these positions as fixed, because they can never be altered later.

What if two different 'T' windows overlap and demand different characters at the same position? Then the requirements contradict each other, and no valid string exists, so we return "" right away. This is why we keep a fixed array: it lets us detect a conflict the moment two 'T' constraints disagree on the same index.

After all 'T' constraints are placed, every remaining unfixed position is still 'a', which is exactly what we want for the smallest string.

Next come the 'F' constraints. These are the opposite: whenever str1[i] == 'F', the window word[i..(i + m - 1)] must not equal t. We only have a problem if this window currently happens to equal t. If it already differs from t, the constraint is satisfied and we do nothing.

When a window does match t and we must break it, we want to make the minimal and smallest change. To keep the string lexicographically small, we should change a position as far to the right as possible (changing later positions affects the order less than changing earlier ones). And to keep that change minimal, we set the character to 'b', the smallest character that differs from 'a'. But we can only modify a position that is not fixed, since fixed positions belong to a 'T' window and changing them would break a hard requirement.

So we scan the window from right to left looking for the first unfixed position and turn it into 'b'. If every position in the window is fixed, then the window is entirely locked to equal t by the 'T' constraints while an 'F' constraint demands it differ—an impossible situation, so we return "".

By always preferring 'a', only escalating to 'b' when absolutely necessary, and always breaking ties at the rightmost free position, we naturally build the lexicographically smallest valid string in a single greedy pass.

Pattern Learn more about Greedy patterns.

Solution Approach

We use a greedy strategy. Let str1 be s and str2 be t, with n = len(s) and m = len(t).

Data structures.

An array ans of length n + m - 1, initialized so that every character is 'a'. This holds the string we are building, and starting with all 'a's keeps it as small as possible by default.
A boolean array fixed of length n + m - 1, initialized to all False. Position k is True once it has been locked by a 'T' constraint and must never be changed again.

Step 1: Apply the 'T' constraints.

We iterate over s with index i. We skip any position where s[i] != 'T'. When s[i] == 'T', the window starting at i must equal t, so we copy t into ans:

For each character c = t[j] (with j from 0 to m - 1), let k = i + j.
If fixed[k] is already True but ans[k] != c, two 'T' windows disagree on the same index, so generation is impossible and we return "".
Otherwise we set ans[k] = c and fixed[k] = True.

After this pass, all hard requirements are stamped in, and every still-unfixed position remains 'a'.

Step 2: Apply the 'F' constraints.

We iterate over s again with index i, skipping any position where s[i] != 'F'. When s[i] == 'F', we check the current window:

If "".join(ans[i : i + m]) != t, the constraint is already satisfied, so we move on.
If the window currently equals t, we must break it. To keep ans lexicographically smallest, we scan the window from right to left, i.e. j from i + m - 1 down to i, and find the first position with fixed[j] == False. We set ans[j] = "b" and stop. Choosing the rightmost free slot and the smallest differing character 'b' makes the minimal possible impact on the order.
If the loop finds no unfixed position (the for ... else branch runs), the entire window is locked to t by 'T' constraints while an 'F' constraint forbids it. This is a contradiction, so we return "".

Step 3: Build the answer.

Finally, we join ans into a string and return it.

Complexity. Each 'T' and 'F' constraint touches at most m positions, and there are at most n constraints, so the time complexity is O(n * m). The space complexity is O(n + m) for the ans and fixed arrays.

Example Walkthrough

Let's trace through a small example to see the greedy approach in action.

Input: str1 = "TFT", str2 = "ab"

So n = 3, m = 2, and the answer length is n + m - 1 = 4.

Initial setup:

index:   0    1    2    3
ans  :  'a'  'a'  'a'  'a'
fixed:   F    F    F    F

Step 1: Apply the 'T' constraints.

We scan str1 = "TFT".

i = 0, s[0] == 'T' → window ans[0..1] must equal "ab".

j = 0: k = 0, c = 'a'. fixed[0] is False, so set ans[0] = 'a', fixed[0] = True.
j = 1: k = 1, c = 'b'. fixed[1] is False, so set ans[1] = 'b', fixed[1] = True.

index:   0    1    2    3
ans  :  'a'  'b'  'a'  'a'
fixed:   T    T    F    F

i = 1, s[1] == 'F' → skip for now (handled in Step 2).

i = 2, s[2] == 'T' → window ans[2..3] must equal "ab".

j = 0: k = 2, c = 'a'. fixed[2] is False, so set ans[2] = 'a', fixed[2] = True.
j = 1: k = 3, c = 'b'. fixed[3] is False, so set ans[3] = 'b', fixed[3] = True.

index:   0    1    2    3
ans  :  'a'  'b'  'a'  'b'
fixed:   T    T    T    T

No conflicts arose, so all hard requirements are satisfied.

Step 2: Apply the 'F' constraints.

We scan str1 = "TFT" again, only acting on 'F'.

i = 1, s[1] == 'F' → window ans[1..2] must not equal "ab".
- Current window: ans[1] + ans[2] = 'b' + 'a' = "ba".
- Since "ba" != "ab", the constraint is already satisfied — do nothing.

The 'F' constraint happened to be broken for free by the surrounding 'T' windows.

Step 3: Build the answer.

index:   0    1    2    3
ans  :  'a'  'b'  'a'  'b'

Joining gives "abab".

Verification:

str1[0] = 'T' → word[0..1] = "ab" == "ab" ✓
str1[1] = 'F' → word[1..2] = "ba" != "ab" ✓
str1[2] = 'T' → word[2..3] = "ab" == "ab" ✓

All constraints hold, and because every free position was kept at the smallest possible character, "abab" is the lexicographically smallest valid string.

A note on the rightmost-'b' rule: In this example the 'F' window was already broken, so we never needed to escalate. To see that mechanism, imagine an 'F' window like ans[1..2] = "ab" where only index 2 is unfixed. We would scan right-to-left, find index 2 free first, and set ans[2] = 'b', turning the window into "ab" → "ab"... wait, into the rightmost free slot to minimize lexicographic impact — choosing a later position to change keeps the earlier (more significant) characters as small as possible.

Solution Implementation

1class Solution:
2    def generateString(self, s: str, t: str) -> str:
3        s_len, t_len = len(s), len(t)
4        total_len = s_len + t_len - 1
5
6        # Result buffer, default-filled with 'a'.
7        result = ["a"] * total_len
8        # Marks positions whose character is forced by a 'T' constraint.
9        is_fixed = [False] * total_len
10
11        # Pass 1: enforce every 'T' window to exactly match t.
12        for start, flag in enumerate(s):
13            if flag != "T":
14                continue
15            for offset, ch in enumerate(t):
16                pos = start + offset
17                # Conflict between two overlapping 'T' windows.
18                if is_fixed[pos] and result[pos] != ch:
19                    return ""
20                result[pos] = ch
21                is_fixed[pos] = True
22
23        # Pass 2: enforce every 'F' window to differ from t.
24        for start, flag in enumerate(s):
25            if flag != "F":
26                continue
27            # Already different — nothing to do.
28            if "".join(result[start : start + t_len]) != t:
29                continue
30            # Try to flip a free (non-fixed) position to break the match.
31            for pos in range(start + t_len - 1, start - 1, -1):
32                if not is_fixed[pos]:
33                    result[pos] = "b"
34                    break
35            else:
36                # Every position is fixed; cannot break the match.
37                return ""
38
39        return "".join(result)
40

1class Solution {
2    public String generateString(String s, String t) {
3        int sLength = s.length();
4        int tLength = t.length();
5
6        // The result string has length n + m - 1 because each position i in s
7        // where s[i] == 'T' means t must start at index i, and the last possible
8        // start index is (n - 1), giving a maximum end index of (n - 1) + (m - 1).
9        int totalLength = sLength + tLength - 1;
10
11        char[] result = new char[totalLength];
12        // Tracks which positions are forced to a specific character by a 'T' constraint.
13        boolean[] fixed = new boolean[totalLength];
14
15        // Default-fill with 'a'; unfixed positions stay 'a' unless changed later.
16        Arrays.fill(result, 'a');
17
18        // Step 1: Apply all 'T' constraints.
19        // For every index i where s[i] == 'T', the substring starting at i must equal t.
20        for (int i = 0; i < sLength; i++) {
21            if (s.charAt(i) != 'T') {
22                continue;
23            }
24            for (int j = 0; j < tLength; j++) {
25                int position = i + j;
26                // Conflict: this position was already fixed to a different character.
27                if (fixed[position] && result[position] != t.charAt(j)) {
28                    return "";
29                }
30                result[position] = t.charAt(j);
31                fixed[position] = true;
32            }
33        }
34
35        // Step 2: Handle all 'F' constraints.
36        // For every index i where s[i] == 'F', the substring starting at i must NOT equal t.
37        for (int i = 0; i < sLength; i++) {
38            if (s.charAt(i) != 'F') {
39                continue;
40            }
41
42            // Check whether the current substring at i already equals t.
43            boolean matchesT = true;
44            for (int j = 0; j < tLength; j++) {
45                if (result[i + j] != t.charAt(j)) {
46                    matchesT = false;
47                    break;
48                }
49            }
50
51            // If it already differs from t, the 'F' constraint is satisfied.
52            if (!matchesT) {
53                continue;
54            }
55
56            // Otherwise we must break the match by altering an unfixed position
57            // within this window. Scanning from the rightmost position is a greedy
58            // choice that minimizes impact on subsequent windows.
59            boolean broken = false;
60            for (int j = i + tLength - 1; j >= i; j--) {
61                if (!fixed[j]) {
62                    result[j] = 'b';
63                    broken = true;
64                    break;
65                }
66            }
67
68            // Every position in the window is fixed and equals t, so the 'F'
69            // constraint cannot be satisfied.
70            if (!broken) {
71                return "";
72            }
73        }
74
75        return new String(result);
76    }
77}
78

1class Solution {
2public:
3    string generateString(string s, string t) {
4        int sLen = s.size();           // Length of the pattern string s (made up of 'T'/'F')
5        int tLen = t.size();           // Length of the substring t to embed
6        int resultLen = sLen + tLen - 1; // Total length of the result string
7
8        // Initialize the answer with all 'a' characters
9        string result(resultLen, 'a');
10        // Track which positions have been forced to a fixed value
11        vector<bool> isFixed(resultLen, false);
12
13        // Step 1: Handle every position where s[i] == 'T'.
14        // A 'T' means an occurrence of t MUST start at index i.
15        for (int i = 0; i < sLen; i++) {
16            if (s[i] != 'T') continue;
17
18            for (int j = 0; j < tLen; j++) {
19                int pos = i + j;
20                // If this position was already fixed to a different char, it's impossible
21                if (isFixed[pos] && result[pos] != t[j]) {
22                    return "";
23                }
24                // Place the required character and mark it as fixed
25                result[pos] = t[j];
26                isFixed[pos] = true;
27            }
28        }
29
30        // Step 2: Handle every position where s[i] == 'F'.
31        // An 'F' means an occurrence of t must NOT start at index i.
32        for (int i = 0; i < sLen; i++) {
33            if (s[i] != 'F') continue;
34
35            // Check whether the current substring already matches t exactly
36            bool matchesT = true;
37            for (int j = 0; j < tLen; j++) {
38                if (result[i + j] != t[j]) {
39                    matchesT = false;
40                    break;
41                }
42            }
43            // If it doesn't match, the 'F' constraint is already satisfied
44            if (!matchesT) continue;
45
46            // It currently matches t, so we must break the match by changing
47            // a non-fixed position (from right to left) to a different char.
48            bool broken = false;
49            for (int j = i + tLen - 1; j >= i; j--) {
50                if (!isFixed[j]) {
51                    result[j] = 'b'; // Any char different from t[j] (t is all 'a' here)
52                    broken = true;
53                    break;
54                }
55            }
56            // If every position in this window is fixed, we cannot break it
57            if (!broken) {
58                return "";
59            }
60        }
61
62        return result;
63    }
64};
65

1/**
2 * Generates a string of length (n + m - 1) over the alphabet {a, b, ...}
3 * such that, for every index i in s:
4 *   - if s[i] === 'T', the substring ans[i..i+m-1] must equal t
5 *   - if s[i] === 'F', the substring ans[i..i+m-1] must NOT equal t
6 *
7 * Returns the constructed string, or '' if no valid string exists.
8 *
9 * @param s - constraint pattern consisting of 'T' / 'F' characters
10 * @param t - the target pattern that each window is compared against
11 * @returns a valid generated string, or '' when impossible
12 */
13function generateString(s: string, t: string): string {
14    const sLength: number = s.length;
15    const tLength: number = t.length;
16
17    // Total length of the result; default every position to 'a'.
18    const resultLength: number = sLength + tLength - 1;
19    const result: string[] = new Array<string>(resultLength).fill('a');
20
21    // Tracks positions that are forced by a 'T' constraint and cannot change.
22    const isFixed: boolean[] = new Array<boolean>(resultLength).fill(false);
23
24    // Step 1: Apply all 'T' constraints.
25    // Each 'T' at index i forces result[i..i+m-1] to exactly match t.
26    for (let i = 0; i < sLength; i++) {
27        if (s[i] !== 'T') {
28            continue;
29        }
30        for (let j = 0; j < tLength; j++) {
31            const position: number = i + j;
32            // Conflict: two 'T' windows demand different characters here.
33            if (isFixed[position] && result[position] !== t[j]) {
34                return '';
35            }
36            result[position] = t[j];
37            isFixed[position] = true;
38        }
39    }
40
41    // Step 2: Apply all 'F' constraints.
42    // Each 'F' at index i requires result[i..i+m-1] to differ from t.
43    for (let i = 0; i < sLength; i++) {
44        if (s[i] !== 'F') {
45            continue;
46        }
47
48        // Check whether the current window already matches t.
49        let matchesTarget: boolean = true;
50        for (let j = 0; j < tLength; j++) {
51            if (result[i + j] !== t[j]) {
52                matchesTarget = false;
53                break;
54            }
55        }
56        // If it already differs, this 'F' constraint is satisfied.
57        if (!matchesTarget) {
58            continue;
59        }
60
61        // The window currently equals t; we must break the match by changing
62        // a non-fixed position within the window to a different character.
63        // Scan from right to left to flip the latest free slot.
64        let resolved: boolean = false;
65        for (let j = i + tLength - 1; j >= i; j--) {
66            if (!isFixed[j]) {
67                result[j] = 'b';
68                resolved = true;
69                break;
70            }
71        }
72        // Every position is fixed and equals t, so we cannot break it.
73        if (!resolved) {
74            return '';
75        }
76    }
77
78    return result.join('');
79}
80

Time and Space Complexity

Time Complexity

The time complexity is O(n × m), where n = len(s) and m = len(t).

The analysis proceeds as follows:

Initialization: Creating the ans and fixed arrays takes O(n + m) time, since their length is n + m - 1.
First loop (handling "T" positions): The outer loop iterates over all n characters of s. For each character equal to "T", the inner loop iterates over all m characters of t, performing constant-time comparisons and assignments. In the worst case (all characters of s are "T"), this contributes O(n × m).
Second loop (handling "F" positions): The outer loop again iterates over all n characters of s. For each character equal to "F", the operation "".join(ans[i : i + m]) != t constructs and compares a substring of length m, costing O(m). The subsequent inner loop scans at most m positions, also O(m). In the worst case (all characters of s are "F"), this contributes O(n × m).
Final join: Joining ans into the result string takes O(n + m).

Combining all parts, the dominant term is O(n × m), so the overall time complexity is O(n × m).

Space Complexity

The space complexity is O(n + m).

The analysis proceeds as follows:

The ans array and the fixed array each have length n + m - 1, requiring O(n + m) space.
In the second loop, the temporary substring created by "".join(ans[i : i + m]) uses O(m) extra space, which does not exceed O(n + m).
The final returned string requires O(n + m) space.

Therefore, the overall space complexity is O(n + m).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Flipping the wrong slot in a `'F'` window breaks lexicographic minimality (or correctness)

The trickiest part of this problem is Step 2, where an 'F' window currently equals t and must be broken by changing one free character. Two related mistakes commonly appear here:

1. Scanning the window left-to-right instead of right-to-left.

A natural-but-wrong instinct is to walk the window from start toward start + t_len - 1 and flip the first free slot found:

# WRONG: flips the leftmost free position
for pos in range(start, start + t_len):
    if not is_fixed[pos]:
        result[pos] = "b"   # changes a more significant character
        break

Changing an earlier index has a much larger impact on lexicographic order than changing a later one. For example, flipping index 2 from 'a' to 'b' produces aaba..., whereas flipping index 5 produces aaaaab..., and aaaaab < aaba. To keep the answer smallest, you must scan from the right end of the window backward and flip the rightmost free position. The provided code does this correctly:

for pos in range(start + t_len - 1, start - 1, -1):
    if not is_fixed[pos]:
        result[pos] = "b"
        break

2. Forgetting that a flipped position is not fixed and can be re-flipped or overwritten.

When we set result[pos] = "b", we deliberately do not mark it as is_fixed. This is correct: only 'T' constraints create hard locks. However, a subtle danger is assuming the single 'b' flip permanently satisfies all later 'F' windows that overlap this position. It does not necessarily — but the algorithm re-checks each 'F' window independently with the up-to-date result, so this stays correct. The pitfall is adding premature is_fixed[pos] = True after a flip "to be safe," which would wrongly block later constraints and can produce spurious "" returns.

Solution / Defensive Reasoning

Always scan right-to-left when breaking an 'F' match, and use 'b' (the smallest character that differs from 'a') only on a free slot.
Never mark a 'b'-flipped slot as fixed. Reserve is_fixed exclusively for 'T'-forced characters.
Trust the for ... else contradiction check. If no free slot exists in an 'F' window, every position is 'T'-locked to t, which is a genuine contradiction → return "".

A deeper correctness subtlety worth verifying

There is one further pitfall hiding in the greedy claim itself. When we flip the rightmost free position to 'b', we assume this single change is enough to make word[start..] differ from t. This holds only because that position is free, meaning the corresponding character of t at that offset is whatever — but result[pos] was 'a' (or possibly already 'b' from an earlier flip). Two cases:

If result[pos] == 'a' and t[pos - start] == 'a', flipping to 'b' correctly creates a mismatch.
If t[pos - start] == 'b' already, then setting result[pos] = 'b' does not break the match!

This is the most easily-missed bug. Consider t = "ab" and a free position aligned with t's 'b': the window is "ab" (because the 'a' slot held 'a' and the 'b' slot held... wait, a free slot defaults to 'a', so the window could only equal "ab" if some 'T' forced the 'b'). In practice, for the window to currently equal t, any free (non-'T') slot must hold 'a', which means t at that offset must also be 'a' — so flipping to 'b' is guaranteed to differ. The greedy is therefore safe, but a robust implementation should make this explicit:

for pos in range(start + t_len - 1, start - 1, -1):
    if not is_fixed[pos]:
        # Pick the smallest char that actually differs from t at this offset.
        result[pos] = "b" if t[pos - start] != "b" else "a"
        break
else:
    return ""

Adding result[pos] = "b" if t[pos - start] != "b" else "a" documents the invariant and guards against any future change to the default-fill character, eliminating the silent failure where a flip leaves the window unchanged.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don't know