LeetCode 3474 | Lexicographically Smallest Generated String | Java | Hard | Greedy | CodeByTushu
Description: π Welcome Back to CodeByTushu!
In todayβs video, we solve LeetCode 3474 β Lexicographically Smallest Generated String using Greedy and String Matching in Java.
We are given two strings str1 of length n and str2 of length m, and we need to construct the lexicographically smallest string word of length n + m - 1 such that the substring starting at index i equals str2 if str1[i] is 'T', and does not equal str2 if str1[i] is 'F'. If no such string can be generated, we return an empty string.
We solve this using a four-phase greedy algorithm. First, we enforce all 'T' constraints by placing str2 at corresponding starting indices, detecting any direct character conflicts and locking these fixed characters. Next, all remaining unassigned positions are greedily initialized to 'a' to achieve minimal lexicographical ordering. Then, we scan all 'F' constraints; whenever a substring matches str2, we greedily mutate the rightmost modifiable character to 'b'. Finally, we perform an O(n * m) verification pass to ensure all conditions hold. The overall time complexity is O(n * m) with O(n + m) auxiliary space.
π₯ Problem Highlights
β Greedy character placement enforcing mandatory 'T' substring matches
β Conflict detection when multiple 'T' constraints overlap incompatibly
β Lexicographically optimal default assignment filling free slots with 'a'
β Rightmost character alteration to resolve forbidden 'F' matches minimally
β Complete linear verification pass confirming all n window constraints
β Optimal O(n * m) time complexity and O(n + m) auxiliary space
β±οΈ TIMESTAMPS
00:00 Intro & Daily Challenge Grand Finale Overview
01:34 Problem Understanding & Constraints Walkthrough
03:43 Key Observations: Mandatory 'T' Propagation & Minimal 'F' Penalty
05:38 Algorithmic Strategy: 4-Phase Greedy Construction
07:21 Clean Java Solution Walkthrough Line by Line
08:30 Dry Run & Step-by-Step Example Walkthrough
10:31 Time Complexity Analysis (O(n * m) - 15 ms, Beats 98.2%)
11:27 Space Complexity Analysis (O(n + m) Auxiliary Space)
12:07 Month Finale Celebration & Wrap-up
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.js
π LeetCode Source Code
π Admin type the link
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Greedy String Construction
Pattern Matching Verification
Lexicographical Optimization
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
When resolving an invalid 'F' constraint where the window currently equals str2, why do we modify the rightmost modifiable character rather than the leftmost?
1οΈβ£ Modifying the rightmost position preserves smaller characters earlier in the string for lexicographical minimality
2οΈβ£ The leftmost character is always locked by previous constraints
3οΈβ£ Modifying the rightmost position guarantees that we never violate subsequent 'T' constraints
4οΈβ£ Modifying from the right requires fewer comparisons
#LeetCode3474 #LeetCode #LexicographicallySmallestGeneratedString #Java #JavaDSA #Greedy #StringMatching #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description
In todayβs video, we solve LeetCode 3474 β Lexicographically Smallest Generated String using Greedy and String Matching in Java.
We are given two strings str1 of length n and str2 of length m, and we need to construct the lexicographically smallest string word of length n + m - 1 such that the substring starting at index i equals str2 if str1[i] is 'T', and does not equal str2 if str1[i] is 'F'. If no such string can be generated, we return an empty string.
We solve this using a four-phase greedy algorithm. First, we enforce all 'T' constraints by placing str2 at corresponding starting indices, detecting any direct character conflicts and locking these fixed characters. Next, all remaining unassigned positions are greedily initialized to 'a' to achieve minimal lexicographical ordering. Then, we scan all 'F' constraints; whenever a substring matches str2, we greedily mutate the rightmost modifiable character to 'b'. Finally, we perform an O(n * m) verification pass to ensure all conditions hold. The overall time complexity is O(n * m) with O(n + m) auxiliary space.
π₯ Problem Highlights
β Greedy character placement enforcing mandatory 'T' substring matches
β Conflict detection when multiple 'T' constraints overlap incompatibly
β Lexicographically optimal default assignment filling free slots with 'a'
β Rightmost character alteration to resolve forbidden 'F' matches minimally
β Complete linear verification pass confirming all n window constraints
β Optimal O(n * m) time complexity and O(n + m) auxiliary space
β±οΈ TIMESTAMPS
00:00 Intro & Daily Challenge Grand Finale Overview
01:34 Problem Understanding & Constraints Walkthrough
03:43 Key Observations: Mandatory 'T' Propagation & Minimal 'F' Penalty
05:38 Algorithmic Strategy: 4-Phase Greedy Construction
07:21 Clean Java Solution Walkthrough Line by Line
08:30 Dry Run & Step-by-Step Example Walkthrough
10:31 Time Complexity Analysis (O(n * m) - 15 ms, Beats 98.2%)
11:27 Space Complexity Analysis (O(n + m) Auxiliary Space)
12:07 Month Finale Celebration & Wrap-up
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/31-March/3474-Lexicographically-Smallest-Generated-String/solution.js
π LeetCode Source Code
π Admin type the link
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Greedy String Construction
Pattern Matching Verification
Lexicographical Optimization
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
When resolving an invalid 'F' constraint where the window currently equals str2, why do we modify the rightmost modifiable character rather than the leftmost?
1οΈβ£ Modifying the rightmost position preserves smaller characters earlier in the string for lexicographical minimality
2οΈβ£ The leftmost character is always locked by previous constraints
3οΈβ£ Modifying the rightmost position guarantees that we never violate subsequent 'T' constraints
4οΈβ£ Modifying from the right requires fewer comparisons
#LeetCode3474 #LeetCode #LexicographicallySmallestGeneratedString #Java #JavaDSA #Greedy #StringMatching #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description
