DEBUG = False # 1. take input N = int(input()) s = input() # 2. generate tile types tile_types = [] # i = tile_size max_size = 2 * 10e5 for i in range(3, 100000): inner = (i-2)**2 outer = i**2 - inner if inner + outer > len(s): break tile_types.append((outer, inner)) # map[tile_type] = (X_count, O_count) = num of Xs & Os in last max subsequence if DEBUG: print("tile_types: ", tile_types) print("num of types: ", len(tile_types)) # 3. initialize state dict state_dict = {} for tile_type in tile_types: state_dict[tile_type[0]] = [0,0] # current X & O counters res = 0 # move one forward, update intermidiate value for (8,1) for i in range(0, len(s)): curr_char = s[i] for tile_type in tile_types: # 1. check if long enough counter = state_dict[tile_type[0]] counter_sum = counter[0] + counter[1] tile_len = tile_type[0] + tile_type[1] if counter_sum == tile_type[0] + tile_type[1]: # decrement if s[i-tile_len] == 'X': counter[0] -= 1 else: counter[1] -= 1 # increment if s[i] == 'X': counter[0] += 1 else: counter[1] += 1 # check if happy if counter[0] == tile_type[0] and counter[1] == tile_type[1]: res += 1 elif counter[0] == tile_type[1] and counter[1] == tile_type[0]: res += 1 else: # increment if s[i] == 'X': counter[0] += 1 else: counter[1] += 1 # check if correct len if counter[0] + counter[1] == tile_len: # check if happy if counter[0] == tile_type[0] and counter[1] == tile_type[1]: res += 1 elif counter[0] == tile_type[1] and counter[1] == tile_type[0]: res += 1 # print("result: ", res) print(res)