Password Irrecoverability Time (reconstructed from Amazon OA variants)

Problem Description

A security team is analyzing how quickly a virus can render a password irrecoverable.

You are given:

• A password string password of length n.
• An array attackOrder of length n, which is a permutation of the integers 1..n (1‑indexed).
• An integer m.

The virus attacks the password over time as follows:

• At second $$t$$ (for $$1 \le t \le n$$), the virus corrupts the character at position attackOrder[t] by replacing it with the malicious character '*'.
  Formally, after second t:
  password[ attackOrder[t] ] = '*' (1‑indexed).

A substring of a string is any contiguous segment of that string. The password is said to be irrecoverable once the number of substrings that contain at least one '*' is greater than or equal to m.

Your task is to compute the minimum time t (in seconds) after which the password becomes irrecoverable:

• If the password is already irrecoverable before any attacks occur (i.e., at time 0 with the initial password), return 1.
• Otherwise, return the smallest t (1 ≤ t ≤ n) such that, after applying the first t attacks, the number of substrings containing at least one '*' is ≥ m.

Some online variants of this problem additionally return -1 if the password never becomes irrecoverable for any t from 1 to n, but this behavior is not specified in the core statement and is usually treated as an implementation choice.

Tags: String, Binary Search, Sliding Window
Difficulty: Medium
Source: Reconstruction from Amazon interview/online assessment variants

Input/Output Format

Assume the problem is implemented as a function:

text int findMinimumTime(string password, vector<int> attackOrder, long long m)

or equivalently in other languages.

• Input

  • password:
    • Type: string
    • Length: n (1 ≤ n).
    • May contain arbitrary characters; positions that are '*' are already malicious from the start.
  • attackOrder:
    • Type: array/list of integers of length n.
    • 1‑indexed permutation of [1, 2, ..., n].
    • attackOrder[t] is the position attacked at second t (1 ≤ attackOrder[t] ≤ n, all distinct).
  • m:
    • Type: 64‑bit integer (long long / long depending on language).
    • Threshold number of substrings that must contain at least one '*' for the password to be considered irrecoverable.

• Output

  • Return an integer t:
    • 1 if the password is already irrecoverable at time 0 (before any attacks).
    • Otherwise, the smallest t in [1, n] such that, after applying the first t attacks, the number of substrings containing at least one '*' is at least m.
    • In some implementations, if no such t exists, -1 is returned; clarify this behavior if unspecified in a real interview.

Examples

Example 1

Input

• password = "abcd"
• attackOrder = [2, 4, 1, 3] (1‑indexed)
• m = 5

Output

• 1

Explanation

1. Length n = 4.
   Total number of substrings of any string of length n is: $$ \text{totalSubstrings} = \frac{n(n+1)}{2} = \frac{4 \cdot 5}{2} = 10 $$

2. Initial state (time 0):

   • Password: "abcd"
   • There are no '*' characters, so 0 substrings contain '*'.
   • 0 < m (= 5), so the password is still recoverable.

3. After 1 second (t = 1):

   • Attack position: attackOrder[1] = 2.
   • Password becomes: "a*cd".
   • Marked positions with '*': index 2.

   Count substrings that contain at least one '*':

   • Treat maximal clean segments (no '*') as:
     • "a" (length 1) before index 2
     • "cd" (length 2) after index 2
   • Number of substrings consisting only of clean characters:
     • For a segment of length k, clean substrings = $$k(k+1)/2$$.
     • "a": $$1 \cdot 2 / 2 = 1$$
     • "cd": $$2 \cdot 3 / 2 = 3$$
     • Total clean substrings = 1 + 3 = 4.
   • Substrings with at least one '*': $$ \text{maliciousSubstrings} = \text{totalSubstrings} - \text{cleanSubstrings} = 10 - 4 = 6 $$
   • 6 ≥ m (= 5), so the password becomes irrecoverable at time t = 1.

4. Since t = 1 is the smallest time at which the malicious substring count reaches at least m, return 1.

Example 2

Input

• password = "abcde"
• attackOrder = [5, 2, 4, 1, 3] (1‑indexed)
• m = 10

Output

• 2

Explanation

1. Length n = 5.
   Total substrings: $$ \text{totalSubstrings} = \frac{5 \cdot 6}{2} = 15 $$

2. Initial state (time 0):

   • Password: "abcde", no '*'.
   • Malicious substrings = 0 < m (= 10). Not irrecoverable.

3. After 1 second (t = 1):

   • Attack position: attackOrder[1] = 5.
   • Password becomes: "abcd*".
   • Clean segments:
     • "abcd" (length 4)
   • Clean substrings:
     • "abcd": $$4 \cdot 5 / 2 = 10$$
   • Malicious substrings: $$ 15 - 10 = 5 < 10 $$
   • Still recoverable.

4. After 2 seconds (t = 2):

   • Attack positions so far: 5 then 2.
   • Password now: "a*cd*" (positions 2 and 5 are '*').
   • Clean segments:
     • "a" (length 1, before index 2)
     • "cd" (length 2, between indices 2 and 5)
   • Clean substrings:
     • "a": $$1 \cdot 2 / 2 = 1$$
     • "cd": $$2 \cdot 3 / 2 = 3$$
     • Total clean substrings = 1 + 3 = 4
   • Malicious substrings: $$ 15 - 4 = 11 \ge 10 $$
   • The password becomes irrecoverable at time t = 2.

5. Since it was not irrecoverable at t = 1 but is irrecoverable at t = 2, the correct answer is 2.

Example 3 (Irrecoverable at the Start)

Input

• password = "*a*"
• attackOrder = [2, 3, 1]
• m = 1

Output

• 1

Explanation

1. Length n = 3, total substrings: $$ \text{totalSubstrings} = \frac{3 \cdot 4}{2} = 6 $$

2. Initial state (time 0):

   • Password already: "*a*" with malicious characters at positions 1 and 3.
   • There is at least one substring containing '*' (for example, "*" at position 1), so the number of malicious substrings is ≥ 1.
   • Therefore, the password is irrecoverable before any virus attacks occur.

3. By the problem requirement, if the password is irrecoverable at the start, the function should return 1.

Constraints

From the problem definition and common interview variants:

• n = len(password)
• attackOrder is a permutation of [1, 2, ..., n] (1‑indexed); all values are distinct and between 1 and n.
• m is an integer threshold; in interesting cases, 1 ≤ m ≤ n(n+1)/2 (the total number of substrings of a string of length n).
• password may already contain '*' characters; those positions are treated as malicious from time 0.

Explicit numeric upper bounds on n and m are not specified in the publicly available statements of this problem. In typical coding‑interview settings, the intended solution runs in:

• Time complexity: $$O(n \log n)$$ — binary search over time t (1..n), with each feasibility check in $$O(n)$$.
• Space complexity: $$O(n)$$ — to track which positions are currently malicious and to scan the string.

Solution Hint

Binary search over the time t from 1 to n, and for a fixed t simulate the first t attacks, then use a linear pass (treating maximal non‑'*' segments as sliding windows) to count clean substrings and derive the number of substrings containing at least one '*' from the total; the smallest t that meets or exceeds m is the answer.