3474. Lexicographically Smallest Generated String Hard

1/**
2 * [3474] Lexicographically Smallest Generated String
3 *
4 * You are given two strings, str1 and str2, of lengths n and m, respectively.
5 * 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:
6 * 
7 * 	If str1[i] == 'T', the <span data-keyword="substring-nonempty">substring</span> of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.
8 * 	If str1[i] == 'F', the <span data-keyword="substring-nonempty">substring</span> of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.
9 * 
10 * Return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span> possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">str1 = "TFTF", str2 = "ab"</span>
15 * Output: <span class="example-io">"ababa"</span>
16 * Explanation:
17 * <h4>The table below represents the string "ababa"</h4>
18 * <table>
19 * 	<tbody>
20 * 		<tr>
21 * 			<th style="border: 1px solid black;">Index</th>
22 * 			<th style="border: 1px solid black;">T/F</th>
23 * 			<th style="border: 1px solid black;">Substring of length m</th>
24 * 		</tr>
25 * 		<tr>
26 * 			<td style="border: 1px solid black;">0</td>
27 * 			<td style="border: 1px solid black;">'T'</td>
28 * 			<td style="border: 1px solid black;">"ab"</td>
29 * 		</tr>
30 * 		<tr>
31 * 			<td style="border: 1px solid black;">1</td>
32 * 			<td style="border: 1px solid black;">'F'</td>
33 * 			<td style="border: 1px solid black;">"ba"</td>
34 * 		</tr>
35 * 		<tr>
36 * 			<td style="border: 1px solid black;">2</td>
37 * 			<td style="border: 1px solid black;">'T'</td>
38 * 			<td style="border: 1px solid black;">"ab"</td>
39 * 		</tr>
40 * 		<tr>
41 * 			<td style="border: 1px solid black;">3</td>
42 * 			<td style="border: 1px solid black;">'F'</td>
43 * 			<td style="border: 1px solid black;">"ba"</td>
44 * 		</tr>
45 * 	</tbody>
46 * </table>
47 * The strings "ababa" and "ababb" can be generated by str1 and str2.
48 * Return "ababa" since it is the lexicographically smaller string.
49 * </div>
50 * <strong class="example">Example 2:
51 * <div class="example-block">
52 * Input: <span class="example-io">str1 = "TFTF", str2 = "abc"</span>
53 * Output: <span class="example-io">""</span>
54 * Explanation:
55 * No string that satisfies the conditions can be generated.
56 * </div>
57 * <strong class="example">Example 3:
58 * <div class="example-block">
59 * Input: <span class="example-io">str1 = "F", str2 = "d"</span>
60 * Output: <span class="example-io">"a"</span>
61 * </div>
62 *  
63 * Constraints:
64 * 
65 * 	1 <= n == str1.length <= 10^4
66 * 	1 <= m == str2.length <= 500
67 * 	str1 consists only of 'T' or 'F'.
68 * 	str2 consists only of lowercase English characters.
69 * 
70 */
71pub struct Solution {}
72
73// problem: https://leetcode.com/problems/lexicographically-smallest-generated-string/
74// discuss: https://leetcode.com/problems/lexicographically-smallest-generated-string/discuss/?currentPage=1&orderBy=most_votes&query=
75
76// submission codes start here
77
78impl Solution {
79    pub fn generate_string(str1: String, str2: String) -> String {
80        String::new()
81    }
82}
83
84// submission codes end
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn test_3474() {
92    }
93}
94