3639. Minimum Time to Activate String Medium

1/**
2 * [3639] Minimum Time to Activate String
3 *
4 * You are given a string s of length n and an integer array order, where order is a <span data-keyword="permutation">permutation</span> of the numbers in the range [0, n - 1].
5 * Starting from time t = 0, replace the character at index order[t] in s with '*' at each time step.
6 * A <span data-keyword="substring-nonempty">substring</span> is valid if it contains at least one '*'.
7 * A string is active if the total number of valid substrings is greater than or equal to k.
8 * Return the minimum time t at which the string s becomes active. If it is impossible, return -1.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">s = "abc", order = [1,0,2], k = 2</span>
13 * Output: <span class="example-io">0</span>
14 * Explanation:
15 * <table style="border: 1px solid black;">
16 * 	<thead>
17 * 		<tr>
18 * 			<th style="border: 1px solid black;">t</th>
19 * 			<th style="border: 1px solid black;">order[t]</th>
20 * 			<th style="border: 1px solid black;">Modified s</th>
21 * 			<th style="border: 1px solid black;">Valid Substrings</th>
22 * 			<th style="border: 1px solid black;">Count</th>
23 * 			<th style="border: 1px solid black;">Active<br />
24 * 			(Count >= k)</th>
25 * 		</tr>
26 * 	</thead>
27 * 	<tbody>
28 * 		<tr>
29 * 			<td style="border: 1px solid black;">0</td>
30 * 			<td style="border: 1px solid black;">1</td>
31 * 			<td style="border: 1px solid black;">"a*c"</td>
32 * 			<td style="border: 1px solid black;">"*", "a*", "*c", "a*c"</td>
33 * 			<td style="border: 1px solid black;">4</td>
34 * 			<td style="border: 1px solid black;">Yes</td>
35 * 		</tr>
36 * 	</tbody>
37 * </table>
38 * The string s becomes active at t = 0. Thus, the answer is 0.
39 * </div>
40 * <strong class="example">Example 2:
41 * <div class="example-block">
42 * Input: <span class="example-io">s = "cat", order = [0,2,1], k = 6</span>
43 * Output: <span class="example-io">2</span>
44 * Explanation:
45 * <table style="border: 1px solid black;">
46 * 	<thead>
47 * 		<tr>
48 * 			<th style="border: 1px solid black;">t</th>
49 * 			<th style="border: 1px solid black;">order[t]</th>
50 * 			<th style="border: 1px solid black;">Modified s</th>
51 * 			<th style="border: 1px solid black;">Valid Substrings</th>
52 * 			<th style="border: 1px solid black;">Count</th>
53 * 			<th style="border: 1px solid black;">Active<br />
54 * 			(Count >= k)</th>
55 * 		</tr>
56 * 	</thead>
57 * 	<tbody>
58 * 		<tr>
59 * 			<td style="border: 1px solid black;">0</td>
60 * 			<td style="border: 1px solid black;">0</td>
61 * 			<td style="border: 1px solid black;">"*at"</td>
62 * 			<td style="border: 1px solid black;">"*", "*a", "*at"</td>
63 * 			<td style="border: 1px solid black;">3</td>
64 * 			<td style="border: 1px solid black;">No</td>
65 * 		</tr>
66 * 		<tr>
67 * 			<td style="border: 1px solid black;">1</td>
68 * 			<td style="border: 1px solid black;">2</td>
69 * 			<td style="border: 1px solid black;">"*a*"</td>
70 * 			<td style="border: 1px solid black;">"*", "*a", "<code inline="">*a*", "<code inline="">a*", "*"</td>
71 * 			<td style="border: 1px solid black;">5</td>
72 * 			<td style="border: 1px solid black;">No</td>
73 * 		</tr>
74 * 		<tr>
75 * 			<td style="border: 1px solid black;">2</td>
76 * 			<td style="border: 1px solid black;">1</td>
77 * 			<td style="border: 1px solid black;">"***"</td>
78 * 			<td style="border: 1px solid black;">All substrings (contain '*')</td>
79 * 			<td style="border: 1px solid black;">6</td>
80 * 			<td style="border: 1px solid black;">Yes</td>
81 * 		</tr>
82 * 	</tbody>
83 * </table>
84 * The string s becomes active at t = 2. Thus, the answer is 2.
85 * </div>
86 * <strong class="example">Example 3:
87 * <div class="example-block">
88 * Input: <span class="example-io">s = "xy", order = [0,1], k = 4</span>
89 * Output: <span class="example-io">-1</span>
90 * Explanation:
91 * Even after all replacements, it is impossible to obtain k = 4 valid substrings. Thus, the answer is -1.
92 * </div>
93 *  
94 * Constraints:
95 * 
96 * 	1 <= n == s.length <= 10^5
97 * 	order.length == n
98 * 	0 <= order[i] <= n - 1
99 * 	s consists of lowercase English letters.
100 * 	order is a permutation of integers from 0 to n - 1.
101 * 	1 <= k <= 10^9
102 * 
103 */
104pub struct Solution {}
105
106// problem: https://leetcode.com/problems/minimum-time-to-activate-string/
107// discuss: https://leetcode.com/problems/minimum-time-to-activate-string/discuss/?currentPage=1&orderBy=most_votes&query=
108
109// submission codes start here
110
111impl Solution {
112    pub fn min_time(s: String, order: Vec<i32>, k: i32) -> i32 {
113        0
114    }
115}
116
117// submission codes end
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122
123    #[test]
124    fn test_3639() {
125    }
126}
127