longest-repeating.py (1433B)
1 import numpy as np 2 3 4 class Solution: 5 def characterReplacement(self, s: str, k: int) -> int: 6 7 # keep track of the most popular as we go through 8 # when adverserial examples are found, we add them to our hash_map 9 # and increment our counter for them. 10 11 # when adverserial > k, we move the left_ptr to the right, removing values each time. 12 # while we do this, we also need to check the most popular character in our 13 # substring. 14 15 longest = 0 16 17 counts = [0] * 26 18 19 left_ptr = 0 20 right_ptr = 0 21 22 converted = [char_to_int(i.lower()) for i in s] 23 24 while right_ptr < len(s): 25 26 counts[converted[right_ptr]] += 1 27 adv = count_adversaries(counts) 28 29 looped = False 30 while count_adversaries(counts) > k: 31 counts[converted[left_ptr]] -= 1 32 left_ptr += 1 33 looped = True 34 35 else: 36 current = (right_ptr - left_ptr) + 1 37 if current > longest: 38 longest = current 39 right_ptr += 1 40 41 return longest 42 43 44 def char_to_int(char_input): 45 return ord(char_input) % 97 46 47 48 def count_adversaries(counts): 49 50 adversaries = 0 51 max_index = np.argmax(counts) 52 for i in range(0, len(counts)): 53 54 if i == max_index: 55 continue 56 adversaries += counts[i] 57 58 return adversaries