You are given a string s of length n and an integer array order, where order is a permutation of the numbers in the range [0, n - 1].
Starting from time t = 0, replace the character at index order[t] in s with '*' at each time step.
A substring is valid if it contains at least one '*'.
A string is active if the total number of valid substrings is greater than or equal to k.
Return the minimum time t at which the string s becomes active. If it is impossible, return -1.
Example 1:
Input: s = "abc", order = [1,0,2], k = 2
Output: 0
Explanation:
t |
order[t] |
Modified s |
Valid Substrings | Count | Active (Count >= k) |
|---|---|---|---|---|---|
| 0 | 1 | "a*c" |
"*", "a*", "*c", "a*c" |
4 | Yes |
The string s becomes active at t = 0. Thus, the answer is 0.
Example 2:
Input: s = "cat", order = [0,2,1], k = 6
Output: 2
Explanation:
t |
order[t] |
Modified s |
Valid Substrings | Count | Active (Count >= k) |
|---|---|---|---|---|---|
| 0 | 0 | "*at" |
"*", "*a", "*at" |
3 | No |
| 1 | 2 | "*a*" |
"*", "*a", ", ", "*" |
5 | No |
| 2 | 1 | "***" |
All substrings (contain '*') |
6 | Yes |
The string s becomes active at t = 2. Thus, the answer is 2.
Example 3:
Input: s = "xy", order = [0,1], k = 4
Output: -1
Explanation:
Even after all replacements, it is impossible to obtain k = 4 valid substrings. Thus, the answer is -1.
Constraints:
1 <= n == s.length <= 105order.length == n0 <= order[i] <= n - 1s consists of lowercase English letters.order is a permutation of integers from 0 to n - 1.1 <= k <= 109Problem Overview: You are given a string and an activation schedule for its positions. Characters become usable only after their activation time. The task is to compute the minimum time when the string satisfies the required activation condition. The core difficulty is determining the earliest time when enough positions are active to validate the constraint.
Approach 1: Time Simulation (Brute Force) (O(n * T) time, O(n) space)
The most direct method simulates time step by step. At each time unit, mark positions whose activation time has been reached and rebuild the current active state of the string. After updating, scan the array to verify whether the required activation condition holds. This approach is easy to implement but inefficient when the maximum time value is large because the string may be rescanned many times.
Approach 2: Binary Search on Time (O(n log n) time, O(n) space)
The key observation is monotonicity: once the string becomes valid at time t, it will remain valid for all later times because more positions only become active. This property allows a binary search over time instead of checking every second. For a candidate time mid, iterate through the array and mark all indices whose activation time is ≤ mid. Then run a validation scan to check whether the string satisfies the problem condition. If the condition holds, shrink the search space to earlier times; otherwise search later times. Each feasibility check is linear.
Approach 3: Optimized Feasibility Check with Prefix Tracking (O(n log n) time, O(n) space)
The feasibility step can be optimized by storing activation states in an auxiliary array and scanning once using prefix logic. Instead of rebuilding the entire string each check, maintain a boolean active array and evaluate the rule directly during the scan. This keeps each binary-search validation strictly O(n) while minimizing overhead. The approach relies on sequential iteration and simple comparisons rather than repeated string reconstruction.
Recommended for interviews: The binary search on time solution is what interviewers expect. Start by explaining the brute-force simulation to show understanding of the problem mechanics, then point out the monotonic property and switch to binary search. The optimized validation step demonstrates practical engineering judgment and keeps the overall complexity at O(n log n).
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Time Simulation (Brute Force) | O(n * T) | O(n) | Good for understanding the activation process or when time range is very small |
| Binary Search on Time | O(n log n) | O(n) | General optimal approach when activation time is monotonic |
| Binary Search + Optimized Check | O(n log n) | O(n) | Preferred in interviews for clean validation and efficient scanning |
3639. Minimum Time to Activate String (Leetcode Medium) • Programming Live with Larry • 723 views views
Watch 7 more video solutions →Practice Minimum Time to Activate String with our built-in code editor and test cases.
Practice on FleetCode