Нужно оптимизировать код при работе с длинной строкой в Python3

Рейтинг: 5Ответов: 3Опубликовано: 27.07.2025

Это задание с Codewars.com

Вам предоставлена строка ввода. Для каждого символа в строке, если это первый встречающийся символ, замените его на "1", в противном случае замените его на количество раз, которое вы уже видели.

Примеры:

input = "Hello, World!" result = "1112111121311"

input = "aaaaaaaaaaaa" result = "123456789101112"

В строке могут содержаться некоторые символы, отличные от ascii.

Моё решение

s = "Hello, World!"
s = '˟ŕ̃Œ̲ɑʕξTȽDZό͈NjΆ̚ΛFȉ̲ɞįɾĹƼg͇πDzʛ˙ȚFŽ˕;ǐ˂­¹˝ə˱ʊƷˈǎͳ˳ƦrΞ˪héΡ˸ɌǟʃćȍǸ»İ˕˰ͨˇɆɱ;ʣ˅Rȅ͆ϣƵ̷Ͱ,§KΔΈêȈƄƪʽˉΥδ\µǟ˘ϧvɚ(nj˶Ƨɪ'
def numericals(s):
    
return ''.join('1' if s.count(v, 0, i + 1) == 1 else str(s.count(v, 0, i + 1)) for i, v in enumerate(s))
return ''.join('1' if s.count(s[i], 0, i + 1) == 1 else str(s.count(s[i], 0, i + 1)) for i in range(len(s)))
return ''.join('1' if s[0:i + 1].count(s[i: i + 1]) == 1 else str(s[0:i + 1].count(s[i: i + 1])) for i in range(0, len(s), 1))

print(numericals(s))

return смотреть снизу - это первое решение - потом второе и третье с enumerate() - последнее

это вроде как моя "ОПТИМИЗАЦИЯ"

Random Tests
random tests - short strings
(20 of 20 Assertions)
random tests - longer strings
(8 of 8 Assertions)

А далее

Execution Timed Out (12000 ms)

Подскажите как сделать оптимизацию и не получить тайм-аут?

python строки алгоритм олимпиада count
Источник: Stack Overflow на русском

Ответы

▲ 7Принят

Ваше решение останавливается на каждой позиции и отсматривает всё начало строки в поисках символа из этой позиции. В позиции i проверяется i + 1 символ (индексация с нуля). Хотя эти просмотры скрыты в вызовах count, тем не менее компьютер обязан их выполнить. А на просмотры уходит время. Для строки длины n компьютер прочитает всего 1 + 2 + 3 + … + (n - 2) + (n - 1) + n символов. Эта сумма равна n(n + 1)/2 – квадратичная сложность. Если оценивать примерно, то удлинение строки в два раза увеличивает время работы программы в четыре раза.

Чтобы сдать кату нужно решить задачу быстрее, например за линию.

collections.Counter придуман чтобы считать одинаковые элементы в последовательностях. В цикле его можно обновлять и спрашивать текущий счётчик. Работает за линейное время:

import collections


def numericals(s):
    counter = collections.Counter()
    
    def gen():
        for c in s: 
            counter.update(c)
            yield str(counter[c])

    return ''.join(gen())
▲ 7

Идея простая: запоминаем букву в словаре как ключ и ведём её счётчик.

Соответственно вопрос:

А как быть если буква повторяется - счетчик будет увеличиваться - и при сравнении со словарём будет указываться её максимальное количество сразу, А надо первый раз появилась - 1, второй раз она же - 2 и т.д.

Решение простое, нам просто нужно добавить список куда мы будем сразу сохранять текущие значение счётчика:

from collections import defaultdict

def numericals(s):
    counts = defaultdict(int)
    result = []

    for char in s:
        counts[char] += 1
        result.append(str(counts[char]))

    return "".join(result)

Или однострочный вариант, но можно наверное и покрасивее придумать:

from collections import defaultdict

def numericals(s):
    return (lambda d: "".join(str(d.update({c: d[c] + 1}) or d[c]) for c in s))(
        defaultdict(int)
    )


print(numericals("Hello, World!"))  # -> 1112111121311
print(numericals("aaaaaaaaaaaa"))  # -> 123456789101112
▲ 1

еще один способ, для общего развития, так сказать.

import pandas as pd
a = "Hello, World!"
df = pd.DataFrame({'letter':list(a), 'count':1})
res = ''.join(df.groupby('letter')['count'].cumsum().astype(str).values)
print(res)