FastPrepFastPrep
Problem Brief

Min Time After Which the Password Becomes Irrecoverable

NEW GRADOA

Database security and authentication have become vital due to the increasing number of cyberattcks 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 the user passwords. The virus designed 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 at the attackOrder[i]-th character of the password, replacing it with the malicious character '*' (source img too blurry, it looks like '*' to me, if not, pls lmk, I am happy to modify accordingly! You are the best! Thanks a lot!), i.e, pwassword[attackOrder[i]] = '*' after the i-th second.

The password is said to be irrecoverable when the number of surroundings of the password containing at least one malicious character '*' becomes greater than or equal to n. In order to estimate the threat posed by the virus, the team wishes to find the min time 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 Description

    Complete the function helpAmazonFindMinTimeAgain in the editor.

    helpAmazonFindMinTimeAgain has the following parameter:

    1. string password: the inital password
    2. int attackOrder[]: permutation arr of integers [1, 2,.., n]
    3. int m: the recoverability parameter

    Returns

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

    1Example 1

    Input
    pwd = "bcced", attackOrder = [2, 3, 1, 4, 5], m = 10
    Output
    2
    Explanation
    Example 1 illustration
    After the first second, the password becomes 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 2nd second, the password becomes: The 11 substrings that containt at least one malicious character are ["b*", "b**", "b**e", "b**ed", "*", "**", "**e", "**ed", "*", "*e", "*ed"]. This is greater or equal to m. After the replacement at second 2, the number of substrings is at least m. The answer is 2. Helloo - I've triple-checked the text, but since the source image is too blurry, if you still find any mistakes, please let me know! I'm more than happy to correct them. Thank you so much! Another source found on the internet - Updated on 05-31-2025 - There is a password of length n = 5, password = "bcced". The 1-based indices where characters will be replaced, attackOrder = [2, 3, 1, 4, 5], and the recoverability parameter m = 10. (1.)  After the 1st second, the password becomes:    b * c e d —— There are 8 substrings that contain at least one malicious character: ["b*", "b*c", "b*ce", "b*ced", "*", "*c", "*ce", "*ced"]. 8 is less than m. (2.)  After the 2nd second, the password becomes:    b * * e d —— There are 11 substrings that contain at least one malicious character: ["b*", "b**", "b**e", "b**ed", "**", "***", "***e", "**ed", "*", "*e", "*ed"]. 11 is greater than or equal to m. After the replacement at 2nd second, the number of substrings is at least m. The answer is 2.

    2Example 2

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

    Constraints

    Limits and guarantees your solution can rely on.

      1 <= n <= 8 * 10^5 String password consists of lowercase English chars 1 <= attackOrder[i] <= n 0 <= m <= n * (n + 1) / 2 
    public int findMinTimeAgain(String pwd, int[] attackOrder, int m) {
  // write your code here
}
    Input

    pwd

    "bcced"

    attackOrder

    [2, 3, 1, 4, 5]

    m

    10

    Output

    2

    Sign in to submit your solution.