m3z9Uxvr

1def findMinimumTime(password: str, attackOrder: list[int], m: int) -> int:
2    N = len(password)
3
4    if N == 0:
5        return 0
6    
7    if m == 0:
8        return 1 # After 1st attack (N>=1), malicious_substring_count > 0, so >= 0.
9
10    total_possible_substrings = N * (N + 1) // 2
11
12    def count_substrings_from_length(k: int) -> int:
13        if k <= 0:
14            return 0
15        return k * (k + 1) // 2
16
17    # This function checks if performing 'num_attacks' makes the password irrecoverable
18    def check(num_attacks: int) -> bool:
19        if num_attacks == 0: # 0 attacks mean 0 malicious substrings
20             return 0 >= m # True only if m is also 0 (handled above) or negative
21
22        is_malicious = [False] * N
23        for i in range(num_attacks):
24            # attackOrder is 1-indexed
25            attack_idx_0_based = attackOrder[i] - 1
26            is_malicious[attack_idx_0_based] = True
27        
28        current_total_clean_substrings = 0
29        current_clean_length = 0
30        for i in range(N):
31            if not is_malicious[i]:
32                current_clean_length += 1
33            else:
34                current_total_clean_substrings += count_substrings_from_length(current_clean_length)
35                current_clean_length = 0
36        current_total_clean_substrings += count_substrings_from_length(current_clean_length) # For the last segment
37
38        num_malicious_substrings = total_possible_substrings - current_total_clean_substrings
39        return num_malicious_substrings >= m
40
41    # Binary search for the minimum number of attacks (time)
42    min_time = N # The answer must be at most N
43    low = 1
44    high = N 
45
46    while low <= high:
47        mid_time = low + (high - low) // 2
48        if mid_time == 0 and m > 0 : # Edge case for binary search reaching 0 if not careful
49             low = mid_time + 1
50             continue
51
52        if check(mid_time):
53            min_time = mid_time # This time works, try smaller
54            high = mid_time - 1
55        else:
56            low = mid_time + 1
57            
58    return min_time