Вот решение в лоб:
text = "CBACBA"
count = 0
for size in range(1, len(text) // 3 + 1):
for pos in range(0, len(text) + 1 - 3 * size):
count_a = 0
count_b = 0
count_c = 0
for index in range(3 * size):
if text[pos + index] == 'A':
count_a += 1
if text[pos + index] == 'B':
count_b += 1
if text[pos + index] == 'C':
count_c += 1
if (count_a == count_b == count_c):
count = count + 1
print(count)
Правда я бы не назвал бы это O(n), скорее O(n(n - 1) / 6) ну т.е. O(n^2) :)
Измененный алгоритм для честных n^2 (плавающее окно):
text = "CBACBA"
count = 0
for step in range(1, len(text) // 3 + 1):
count_a = 0
count_b = 0
count_c = 0
size = step * 3
for pos in range(size):
if text[pos] == 'A':
count_a = count_a + 1
if text[pos] == 'B':
count_b = count_b + 1
if text[pos] == 'C':
count_c = count_c + 1
if (count_a == count_b == count_c):
count = count + 1
for pos in range(1, len(text) + 1 - size):
if text[pos - 1] == 'A':
count_a = count_a - 1
if text[pos - 1] == 'B':
count_b = count_b - 1
if text[pos - 1] == 'C':
count_c = count_c - 1
if text[pos + size - 1] == 'A':
count_a = count_a + 1
if text[pos + size - 1] == 'B':
count_b = count_b + 1
if text[pos + size - 1] == 'C':
count_c = count_c + 1
if (count_a == count_b == count_c):
count = count + 1
print(count)
По совету @Danis включил словари для уменьшения кода:
text = "CBACBA"
total_count = 0
for step in range(1, len(text) // 3 + 1):
local_count = {"A": 0, "B": 0, "C": 0}
size = step * 3
for pos in range(size):
local_count[text[pos]] += 1
if (local_count['A'] == local_count['B'] == local_count['C']):
total_count += 1
for pos in range(1, len(text) + 1 - size):
local_count[text[pos - 1]] -= 1
local_count[text[pos + size - 1]] += 1
if (local_count['A'] == local_count['B'] == local_count['C']):
total_count += 1
print(total_count)