By Expert Funda Tuesday, March 31, 2026

LeetCode 3474 – Lexicographically Smallest Generated String

LeetCode 3474 – Lexicographically Smallest Generated String | ExpertFunda

3474 Hard Weekly Contest 440

Lexicographically Smallest Generated String

Given a boolean pattern str1 and a template str2, construct the lexicographically smallest string word of length n+m−1 such that every T-window equals str2 and every F-window differs. Return "" if impossible.

O(n·m)Time

O(n+m)Space

3Phases

JavaLanguage

📄

Problem Statement

You are given two strings str1 and str2.

str1 consists only of 'T' and 'F' characters. str2 is any string.

A string word of length n + m - 1 (where n = str1.length(), m = str2.length()) is called valid if:

For every index i from 0 to n-1:

• If str1[i] == 'T' → the substring word[i..i+m-1] must equal str2.

• If str1[i] == 'F' → the substring word[i..i+m-1] must not equal str2.

Return the lexicographically smallest valid word, or "" if no valid word exists.

Constraints

1 <= str1.length() <= 10⁵
1 <= str2.length() <= 10⁵
str1 consists only of 'T' and 'F'
str2 consists of lowercase English letters

📝

Examples

Example 1

str1"TFTF"

str2"ab"

Output"ababa"

Stamp "ab" at i=0 and i=2. Free cell at index 4 stays 'a'. F-windows at i=1,3 both yield "ba" ≠ "ab". Valid and lexicographically smallest.

Example 2

str1"TF"

str2"aa"

Output"aab"

Stamp "aa" at i=0 → word="aa?". Free cell word[2] gets 'a'. But word[1..2]="aa"=str2 — F constraint violated! Bump word[2] to 'b' → "aab". Valid.

Example 3

str1"T"

str2"abc"

Output"abc"

Only one position. str1[0]='T' forces word[0..2]="abc". No F-positions to check. Answer is "abc".

Example 4 — Impossible

str1"TT"

str2"ab"

Output""

i=0 forces word[1]='b'. i=1 forces word[1]='a'. Conflict on shared cell → return "".

💡

Intuition

⚙

Core idea: Think of T-positions as stamps — you physically imprint str2 onto the output canvas at each T index. F-positions are guards — they reject any window that accidentally looks like str2.

To get the lexicographically smallest result, start by filling every cell with 'a'. Then override only what the T-stamps force. After stamping, free cells already hold 'a' — the smallest possible character.

For F-guards: if after all stamps the window at an F index equals str2, we must break the match. We scan the window right-to-left for the rightmost free (unfixed) cell and bump it up by one character. Using the rightmost cell preserves the smallest possible prefix — maximizing lexicographic minimality.

⚠

Conflict detection: Two overlapping T-stamps disagree on a shared cell → return "". An F-window fully fixed by T-stamps equals str2 with no free cell to bump → return "".

🔄

Step-by-Step Approach

Initialize word[] and fixed[]

Create word of length n+m-1, filled with 'a'. Create a boolean array fixed[] (all false) to track which cells are locked by a T-stamp.

Phase 2 — Stamp T-positions

For each i where str1[i]=='T', copy str2 into word[i..i+m-1]. Before each write, if the cell is already fixed and the value differs → conflict, return "". Then mark fixed[i+j]=true.

Phase 3 — Verify F-positions

For each i where str1[i]=='F', check if word[i..i+m-1] equals str2. If yes — scan right-to-left for the rightmost free cell and bump its character by +1. If all cells are fixed → impossible, return "".

Return result

All constraints satisfied. Return new String(word). The result is guaranteed to be lexicographically smallest because we started from all-'a' and bumped only the minimum necessary cell as late (rightmost) as possible.

💻

Java Solution

Java Greedy + Forced-Cell Fix

import java.util.Arrays;

class Solution {
    public String generateString(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int len = n + m - 1;

        // Phase 1 — init all 'a' (lexicographically smallest base)
        char[] word = new char[len];
        Arrays.fill(word, 'a');
        boolean[] fixed = new boolean[len];

        // Phase 2 — stamp str2 at every T-position
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'T') {
                for (int j = 0; j < m; j++) {
                    // Conflict: two T-stamps disagree on same cell
                    if (fixed[i + j] && word[i + j] != str2.charAt(j))
                        return "";
                    word[i + j] = str2.charAt(j);
                    fixed[i + j] = true;
                }
            }
        }

        // Phase 3 — verify F-positions; fix if window accidentally = str2
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'F') {
                boolean equal = true;
                for (int j = 0; j < m; j++) {
                    if (word[i + j] != str2.charAt(j)) {
                        equal = false;
                        break;
                    }
                }
                if (equal) {
                    // Scan right-to-left: bump rightmost free cell
                    boolean bumped = false;
                    for (int j = m - 1; j >= 0; j--) {
                        if (!fixed[i + j]) {
                            word[i + j] = (char) (str2.charAt(j) + 1);
                            bumped = true;
                            break;
                        }
                    }
                    // All cells fixed — impossible to satisfy F constraint
                    if (!bumped) return "";
                }
            }
        }
        return new String(word);
    }
}

⚙

Dry Run — `str1="TFTF"`, `str2="ab"`

Phase	i	j	Action	word[]	fixed[]
Init	—	—	fill 'a', fixed=false	a a a a a	F F F F F
Stamp T	0	0	word[0]='a', fixed[0]=T	a a a a a	T F F F F
Stamp T	0	1	word[1]='b', fixed[1]=T	a b a a a	T T F F F
Skip F	1	—	str1[1]='F' — skip stamp	a b a a a	T T F F F
Stamp T	2	0	word[2]='a', fixed[2]=T	a b a a a	T T T F F
Stamp T	2	1	word[3]='b', fixed[3]=T	a b a b a	T T T T F
Skip F	3	—	str1[3]='F' — skip stamp	a b a b a	T T T T F
Check F	1	—	word[1..2]="ba" ≠ "ab" ✓	a b a b a	T T T T F
Check F	3	—	word[3..4]="ba" ≠ "ab" ✓	a b a b a	T T T T F
Return	"ababa" — all constraints satisfied			a b a b a	T T T T F

📈

Complexity Analysis

Metric	Value	Reason
Time — Phase 2	O(n · m)	For each of n positions, we write up to m characters.
Time — Phase 3	O(n · m)	For each F position, we compare up to m characters.
Total Time	O(n · m)	Dominated by Phase 2 + Phase 3 window scans. KMP upgrades this to O(n+m).
Space	O(n + m)	`word[]` and `fixed[]` each hold n+m−1 entries.

⚖

Other Approaches

Greedy Stamp + Forced-Cell Fix

Stamp T-positions, fill free cells with 'a', scan F-positions and bump the rightmost free cell if needed. Simplest to implement correctly under contest pressure.

O(n·m) Recommended

KMP Failure Function

Use KMP's partial-match table to check F-windows and locate the bump cell in O(1) per window. Optimal time complexity.

O(n+m) Optimal

Z-Function Approach

Build S = str2 + "#" + word and compute Z-array. Z[i+m+1]==m identifies matching windows. Elegant but less intuitive than KMP.

O(n+m) Advanced

Brute-Force Backtracking

Try every character at each free cell, check all constraints, backtrack. Only viable for tiny inputs as a conceptual prototype. TLE on judge.

Exponential TLE

🌟

Key Takeaways

📌

Start from all 'a': The lexicographically smallest base lets you override only what's forced, guaranteeing minimality without extra comparison.

📌

Rightmost free cell for bump: Changing the rightmost possible cell in an F-window disturbs the smallest prefix — this is the secret to keeping the output lex-smallest.

📌

fixed[] is the key guard: Tracking which cells are locked by T-stamps lets you detect conflicts instantly and know which cells are safe to modify for F-fixes.

ExpertFunda Team

LeetCode Solutions & DSA Tutorials

Java DSA Weekly Contest

🔗