Quick Overview

This question evaluates understanding of combinatorics, string processing, and algorithmic data structures for efficiently tracking dynamic intervals and counting contiguous substrings as characters are corrupted over time.

Find earliest time password becomes irrecoverable

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given a password string of length n and an attack order array attackOrder[1..n], a permutation of 1..n. At second i (1-indexed), the virus replaces the character at position attackOrder[i] with a malicious character '*'. A substring is contiguous. The password becomes irrecoverable when the number of substrings containing at least one '*' is >= m. Find the minimum time t (1 <= t <= n) after which the password is irrecoverable. Special rule: if the password is considered irrecoverable at the start, report 1. Constraints: 1 <= n <= 8e5; password is lowercase letters; 1 <= attackOrder[i] <= n; 0 <= m <= n*(n+ 1)/2.

Overview: This question evaluates understanding of combinatorics, string processing, and algorithmic data structures for efficiently tracking dynamic intervals and counting contiguous substrings as characters are corrupted over time.

You are given a password string of length n and an array attack_order[1..n], a permutation of 1..n. At second i (1-indexed), the character at position attack_order[i] is replaced by '*'. A substring is contiguous. The password is irrecoverable when the number of substrings containing at least one '*' is at least m. Find the minimum t (1 <= t <= n) such that after t seconds the password is irrecoverable. Special rule: if m == 0, return 1.

Constraints

  • 1 <= n <= 8e5
  • password consists of lowercase English letters
  • attack_order is a permutation of 1..n (1-indexed positions)
  • 0 <= m <= n*(n+1)/2
  • Return the minimal t in [1..n]; if m == 0, return 1

Hints

  1. The number of substrings containing '*' is non-decreasing over time; use binary search on t.
  2. For a fixed t, positions attacked by time t split the array into clean segments; substrings without '*' are the sum over segments of len*(len+1)/2.
  3. Precompute the attack time for each position to check any t in O(n).

Loading coding console...

Show the approach

Approach

Map each position to the time it is attacked. For a given time t, positions with attack time > t are still clean; they form maximal clean segments. The number of substrings without '' at time t is the sum over clean segments of len(len+1)/2. Substrings with '*' equal total_substrings minus that sum. This count is monotonic in t, enabling a binary search over t in [1..n]. The special case m==0 requires returning 1 by rule.

Time complexity:
O(n log n)
Space complexity:
O(n)