Оптимизированный счетчик частоты символа в строке

Question

Я решал этот вопрос, который требует подсчитать количество 'a' в строке после выполнения манипуляции с ней до строки 6.

И решение, которое я придумал, таково:

s='abcac'
n=52
x=n//len(s)
y=n%len(s)
k=s[:y]
s=(s*x)+k
from collections import Counter
print(s.count('a'))

- довольно просто и просто. Но это дает ошибку, когда n большое число, например, 1000000000000.

Как я могу оптимизировать свое решение? Заранее спасибо .

Answer 1

Вам не нужно создавать расширенную строку.Сначала посчитайте количество полных повторений вашей строки, которое будет соответствовать n символам: n//len(s).Затем умножьте это количество на число «а» в строке.Если у вас есть это, вам нужно только выяснить, сколько еще вашей строки нужно, чтобы покрыть оставшуюся часть символов n: n%len(s), и подсчитать число «a» в этой подстроке:

Итак, результат будет просто:

 n//len(s)*s.count("a") + s[:n%len(s)].count("a")

Answer 2

Вы упоминаете, что «выдает ошибку, когда n большое число, например, 1000000000000».Давайте посмотрим, что мы делаем с n ...

Переменная n - это количество символов с самого начала, которые нас интересуют.Кроме того, x = n // len(s), x - это число полных повторений строки s, с которыми мы столкнемся, а y - это подстрока, которая заботится о любом "остатке" / "переполнения"" буквы.

Теперь большой красный флаг для меня - это как s = (s * x) + k.Синтаксически это нормально - python поддерживает строковое умножение.Но давайте посмотрим, что происходит в моем интерпретаторе, когда я запускаю ваш код и делаю n очень очень большим ...

>>> string * 10000000000000000
python(<pid>,<memory-address>) malloc: *** mach_vm_map(size=10000000000004096) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>>

Когда мы создаем такую ​​расширенную строку, требуется память для ее хранения - иесли каждый символ строки составляет 1 байт (для простоты предположим только символы ASCII), эта строка требует 10 ^ 12 или около одного терабайта информации!Это невыполнимо.

Я думаю, что задача здесь состоит в том, чтобы найти решение, которое не требует от вас фактического создания строки - есть математические способы, которыми вы можете вычислить число «а» в бесконечной строке, даннойчто вы знаете его подструктуру.

Для справки, вот мое решение:

def repeatedString(s, n):
    num_a_in_substring = s.count('a')
    n_repetitions = n // len(s)
    overflow = s[:n%len(s)]
    return (num_a_in_substring * n_repetitions) + overflow.count('a')

Обратите внимание, как вместо создания гигантской версии в памяти нашей чудовищной строки из 10 ^ 12 символов,Я вычисляю число «а» в меньшей строке и строю из этого результата.Таким образом, я просто жонглирую числом вместо гигантской строки.

Надеюсь, это поможет.

Answer 3

from collections import Counter
s='a'
n=100000
a=s.count('a')
x=n//len(s)
y=n%len(s)
k=s[:y]
b=k.count('a')
#s=(s*x)+k
print((a*x)+b)

Я изменил код на это, и он добился цели. Большое спасибо всем за помощь.

Довольно очевидное решение, как-то я его пропустил.