Мой простой цикл while подвешивает мой компьютер на больших входах

Question

Это мой ответ на вызов HackerRank

https://www.hackerrank.com/challenges/repeated-string

def repeatedString(s, n):
   string = ''
   count = 0

   while len(string) < n:
      for letter in s:
         if len(string) != n:
            string += letter
            if letter == 'a':
               count += 1
   return count

print(repeatedString('aba', 10))
>> 7 # works!

's' является строковым вводом, например. «abc», что теоретически повторяется вечно. 'n' - количество символов, которое мне нужно использовать для этой бесконечной строки, например. 'abcabcabca', если n = 10

Затем мне нужно найти количество вхождений 'a', моя функция отлично работает с маленькими целыми числами, но для тестового случая, о котором идет речь, они используют 1000000000000 и все время ожидания, даже на моем ноутбуке.

Есть ли более эффективный и менее ресурсоемкий способ сделать это?

Answer 1

Вы можете просто сделать математику вместо цикла:

def repeatedString(s, n):
   q, r = divmod(n, len(s))
   return s.count('a') * q + s[:r].count('a')

Значение n не имеет значения для этого решения. repeatedString('abca', 100000000000000000000000) работает только на 30% медленнее, чем repeatedString('abca', 10).