Minimum time to activate string

Array Binary Search

49.2% acceptance

Feb 25, 2026

120

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_time(s: String, order: Vec<i32>, k: i32) -> i32 {
    let n = s.len() as i64;
    // Total substrings = n*(n+1)/2
    // A string has valid_count = total - invalid_count
    // Invalid substrings: those containing no '*' = segments between stars
    // If stars are at positions p1 < p2 < ... < pm, the "non-star" segments are:
    // [0, p1-1], [p1+1, p2-1], ..., [pm+1, n-1]
    // Each segment of length L contributes L*(L+1)/2 invalid substrings.
    //
    // We maintain the lengths of contiguous non-star segments.
    // Use a union-find or sorted set to track boundaries.
    // 
    // Binary search on time t:
    // Check if at time t, valid_count >= k.
    
    // Use binary search on t in [0, n-1], and for each t compute valid count.
    // For a given set of star positions, we compute sum of segment lengths.
    // We can use a simple approach: for time t, the stars are at order[0..=t].
    // The invalid count = sum of tri(len) for each non-star segment.
    // tri(l) = l*(l+1)/2
    
    let total = n * (n + 1) / 2;
    let k = k as i64;
    
    // Build time-at-index: time_at[i] = t when position i gets starred
    let mut time_at = vec![0usize; n as usize];
    for (t, &pos) in order.iter().enumerate() {
      time_at[pos as usize] = t;
    }
    
    // Binary search on t
    let compute_invalid = |t: usize| -> i64 {
      // positions starred: those with time_at[i] <= t
      // Find contiguous non-starred segments
      let mut invalid = 0i64;
      let mut seg_len = 0i64;
      for i in 0..n as usize {
        if time_at[i] <= t {
          // star at i: close current segment
          invalid += seg_len * (seg_len + 1) / 2;
          seg_len = 0;
        } else {
          seg_len += 1;
        }
      }
      invalid += seg_len * (seg_len + 1) / 2;
      invalid
    };
    
    // Check if even after all stars it's possible
    let invalid_at_end = compute_invalid(n as usize - 1);
    if total - invalid_at_end < k {
      return -1;
    }
    
    // Binary search for smallest t
    let mut lo = 0i64;
    let mut hi = n - 1;
    while lo < hi {
      let mid = (lo + hi) / 2;
      let inv = compute_invalid(mid as usize);
      if total - inv >= k {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo as i32
  }
}