LeetCode 3474 – Lexicographically Smallest Generated String
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() <= 1051 <= str2.length() <= 105str1consists only of'T'and'F'str2consists 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
1
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.2
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.3
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 "".4
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.