Find earliest time password becomes irrecoverable
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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.
Quick Answer: 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
Solution
from typing import List
def earliest_irrecoverable_time(password: str, attack_order: List[int], m: int) -> int:
n = len(password)
if m <= 0:
return 1
total_substrings = n * (n + 1) // 2
# time_attacked[i] = time when position i (0-based) is attacked (1..n)
time_attacked = [0] * n
for i, pos in enumerate(attack_order):
time_attacked[pos - 1] = i + 1 # convert to 0-based index
def substrings_with_star(t: int) -> int:
# Count substrings that contain at least one '*'
# = total_substrings - substrings without '*'
clean_sum = 0
run = 0
for i in range(n):
if time_attacked[i] > t: # still clean at time t
run += 1
else:
if run:
clean_sum += run * (run + 1) // 2
run = 0
if run:
clean_sum += run * (run + 1) // 2
return total_substrings - clean_sum
lo, hi = 1, n
ans = n
while lo <= hi:
mid = (lo + hi) // 2
if substrings_with_star(mid) >= m:
ans = mid
hi = mid - 1
else:
lo = mid + 1
return ansExplanation
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).
Hints
- The number of substrings containing '*' is non-decreasing over time; use binary search on t.
- 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.
- Precompute the attack time for each position to check any t in O(n).