Skip to main content
Talentd

Minimum Time to Activate String - Solution & Explanation

MediumArrayBinary Search4 min readAsked at: Amazon
Practice this problem

Problem Statement

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", "*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 <= 105
  • order.length == n
  • 0 <= order[i] <= n - 1
  • s consists of lowercase English letters.
  • order is a permutation of integers from 0 to n - 1.
  • 1 <= k <= 109

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TimeO(n log n)O(n)General optimal approach when activation time is monotonic
Binary Search + Optimized CheckO(n log n)O(n)Preferred in interviews for clean validation and efficient scanning

Video Solution

3639. Minimum Time to Activate String (Leetcode Medium) • Programming Live with Larry • 741 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Time to Activate String easy or hard?
Minimum Time to Activate String is generally classified as a Medium problem. The array processing itself is straightforward, but recognizing the monotonic property that enables binary search is the key insight that raises the difficulty.
Minimum Time to Activate String Python/Java solution
Implement binary search over time and write a helper function that checks whether the string is valid given a time limit. The helper scans the array and marks active positions before evaluating the constraint. The same logic translates directly across Python, Java, and C++ with identical O(n log n) complexity.
How to solve Minimum Time to Activate String in O(n log n)?
Use binary search on the answer. Pick a candidate time mid and mark all positions whose activation time is less than or equal to mid. Perform a linear scan to check whether the string satisfies the activation requirement using those active indices. If the condition holds, move the search left to find a smaller time; otherwise move right.
What is the best approach for Minimum Time to Activate String?
Binary search on time is the most efficient strategy. The activation condition is monotonic: if the string becomes valid at time t, it remains valid for any time greater than t. This allows searching the minimum feasible time with O(log n) iterations while each feasibility check scans the array in O(n). The total complexity becomes O(n log n).
Is Minimum Time to Activate String asked at Google/Amazon/Meta?
Problems combining array scanning with binary search on the answer frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include scheduling problems, activation timelines, and feasibility checks where a monotonic condition allows binary search.
What data structure is used in Minimum Time to Activate String?
The solution mainly uses arrays and simple boolean tracking for activation states. Binary search controls the time range, while a linear pass over the array validates whether the currently activated indices satisfy the condition.
What is the time complexity of Minimum Time to Activate String?
The optimal solution runs in O(n log n) time and O(n) space. Binary search is performed over the time range, and each step checks whether the string can be considered activated by scanning the array once. The brute force simulation alternative may degrade to O(n * T) depending on the maximum time value.

Ready to solve this problem?

Practice Minimum Time to Activate String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays