FastPrep
Problem · Binary Search

Min Time After Which the Password Becomes Irrecoverable

Learn this problem
● HardAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Database security and authentication have become vital due to the increasing number of cyberattacks every day. Amazon has created a team for the analysis of various types of cyberattacks. In one such analysis, the team finds a virus that attacks user passwords. The virus has an attacking rule defined by attackOrder, which is a permutation of length n.

In the i-th second of the attack, the virus attacks the attackOrder[i]-th character (1-based) of the password, replacing it with the malicious character *. That is, after the i-th second, password[attackOrder[i]] = '*'.

The password is said to be irrecoverable when the number of substrings of the password containing at least one malicious character * becomes greater than or equal to m. The team wishes to find the minimum time (in seconds) after which the password becomes irrecoverable.

Note:

  • If the password is irrecoverable at the start, report 1 as the answer.
  • A substring of a string s is a contiguous segment of that string.

Function

findMinTimeAgain(pwd: String, attackOrder: int[], m: int) → int

Complete the function findMinTimeAgain in the editor.

findMinTimeAgain has the following parameters:

  • string password: the initial password
  • int attackOrder[]: a permutation of the integers [1, 2, ..., n] giving the attack order
  • int m: the recoverability parameter

Returns

int: the minimum time after which the password becomes irrecoverable.

Examples

Example 1

pwd = "bcced"attackOrder = [2, 3, 1, 4, 5]m = 10return = 2

There is a password of length n = 5, password = "bcced". The 1-based indices where characters will be replaced are attackOrder = [2, 3, 1, 4, 5], and the recoverability parameter is m = 10.

After the 1st second, the password becomes b*ced. The 8 substrings that contain at least one malicious character are ["b*", "b*c", "b*ce", "b*ced", "*", "*c", "*ce", "*ced"], and 8 is less than m.

After the 2nd second, the password becomes b**ed. The 11 substrings that contain at least one malicious character are ["b*", "b**", "b**e", "b**ed", "*", "**", "**e", "**ed", "*", "*e", "*ed"], and 11 is greater than or equal to m.

After the replacement at second 2, the number of such substrings is at least m. The answer is 2.

Example 2

pwd = "abcd"attackOrder = [4, 1, 3, 2]m = 10return = 4
This test case was added on 06-03-2025. Relevant source ss was included in the Problem Source section below.

Constraints

  • 1 <= n <= 8 * 10^5, where n is the length of password
  • password consists of lowercase English characters
  • attackOrder is a permutation of [1, 2, ..., n], so 1 <= attackOrder[i] <= n
  • 0 <= m <= n * (n + 1) / 2

More Amazon problems

drafts saved locally
public int findMinTimeAgain(String pwd, int[] attackOrder, int m) {
  // write your code here
}
pwd"bcced"
attackOrder[2, 3, 1, 4, 5]
m10
expected2
checking account