In this guide, you will get 3474. Lexicographically Smallest Generated String LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest Generated String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Lexicographically Smallest Generated String
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 "".
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.
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 <= 104
1 <= m == str2.length <= 500
str1 consists only of 'T' or 'F'.
str2 consists only of lowercase English characters.
Complexity Analysis
Time Complexity: O(nm)
Space Complexity: O(n + m)
3474. Lexicographically Smallest Generated String LeetCode Solution in C++
class Solution {
public:
string generateString(string str1, string str2) {
const int n = str1.length();
const int m = str2.length();
const int sz = n + m - 1;
string ans(sz, '\0');
vector<bool> modifiable(sz, true);
// 1. Handle all 'T' positions first.
for (int i = 0; i < n; ++i)
if (str1[i] == 'T')
for (int j = 0; j < m; ++j) {
const int pos = i + j;
if (ans[pos] && ans[pos] != str2[j])
return "";
ans[pos] = str2[j];
modifiable[pos] = false;
}
// 2. Fill all remaining positions with 'a'.
for (int i = 0; i < sz; ++i)
if (ans[i] == '\0')
ans[i] = 'a';
// 3. Handle all 'F' positions.
for (int i = 0; i < n; ++i)
if (str1[i] == 'F' && match(ans, i, str2)) {
const int modifiablePos = lastModifiablePosition(i, m, modifiable);
if (modifiablePos == -1)
return "";
ans[modifiablePos] = 'b';
modifiable[modifiablePos] = false;
}
return ans;
}
private:
// Returns true if the substring of ans starting at `i` matches `s`.
bool match(string& ans, int i, string& s) {
for (int j = 0; j < s.length(); ++j)
if (ans[i + j] != s[j])
return false;
return true;
}
// Finds the last modifiable position in the substring ans starting at `i`.
int lastModifiablePosition(int i, int m, vector<bool>& modifiable) {
int modifiablePos = -1;
for (int j = 0; j < m; ++j) {
const int pos = i + j;
if (modifiable[pos])
modifiablePos = pos;
}
return modifiablePos;
}
}; /* code provided by PROGIEZ */
3474. Lexicographically Smallest Generated String LeetCode Solution in Java
class Solution {
public String generateString(String str1, String str2) {
final int n = str1.length();
final int m = str2.length();
final int sz = n + m - 1;
char[] ans = new char[sz];
boolean[] modifiable = new boolean[sz];
Arrays.fill(modifiable, true);
// 1. Handle all 'T' positions first.
for (int i = 0; i < n; ++i)
if (str1.charAt(i) == 'T')
for (int j = 0; j < m; ++j) {
final int pos = i + j;
if (ans[pos] != 0 && ans[pos] != str2.charAt(j))
return "";
ans[pos] = str2.charAt(j);
modifiable[pos] = false;
}
// 2. Fill all remaining positions with 'a'.
for (int i = 0; i < sz; ++i)
if (ans[i] == 0)
ans[i] = 'a';
// 3. Handle all 'F' positions.
for (int i = 0; i < n; ++i)
if (str1.charAt(i) == 'F' && match(ans, i, str2)) {
final int modifiablePos = lastModifiablePosition(i, m, modifiable);
if (modifiablePos == -1)
return "";
ans[modifiablePos] = 'b';
modifiable[modifiablePos] = false;
}
return new String(ans);
}
// Returns true if the substring of ans starting at `i` matches `s`.
private boolean match(char[] ans, int i, String s) {
for (int j = 0; j < s.length(); ++j)
if (ans[i + j] != s.charAt(j))
return false;
return true;
}
// Finds the last modifiable position in the substring ans starting at `i`.
private int lastModifiablePosition(int i, int m, boolean[] modifiable) {
int modifiablePos = -1;
for (int j = 0; j < m; ++j) {
final int pos = i + j;
if (modifiable[pos])
modifiablePos = pos;
}
return modifiablePos;
}
} // code provided by PROGIEZ
3474. Lexicographically Smallest Generated String LeetCode Solution in Python
class Solution:
def generateString(self, str1: str, str2: str) -> str:
n = len(str1)
m = len(str2)
sz = n + m - 1
ans = [None] * sz
modifiable = [True] * sz
# 1. Handle all 'T' positions first.
for i, tf in enumerate(str1):
if tf == 'T':
for j, c in enumerate(str2):
pos = i + j
if ans[pos] and ans[pos] != c:
return ''
ans[pos] = c
modifiable[pos] = False
# 2. Fill all remaining positions with 'a'.
for i in range(sz):
if not ans[i]:
ans[i] = 'a'
# 3. Handle all 'F' positions.
for i in range(n):
if str1[i] == 'F' and self._match(ans, i, str2):
modifiablePos = self._lastModifiablePosition(i, m, modifiable)
if modifiablePos == -1:
return ''
ans[modifiablePos] = 'b'
modifiable[modifiablePos] = False
return ''.join(ans)
def _match(self, ans: list, i: int, s: str) -> bool:
"""Returns True if the substring of ans starting at `i` matches `s`."""
for j, c in enumerate(s):
if ans[i + j] != c:
return False
return True
def _lastModifiablePosition(self, i: int, m: int, modifiable: list) -> int:
"""
Finds the last modifiable position in the substring of ans starting at `i`.
"""
modifiablePos = -1
for j in range(m):
pos = i + j
if modifiable[pos]:
modifiablePos = pos
return modifiablePos # code by PROGIEZ
