Count occurrences of a letter in a string that repeats several times to a character limit

Question

In this problem I have to count the number of times the letter appears 'a' in string 'a' range 1000000000000, only that I have run time error when it is a very high number like this. for example: if I put up 100000 I can count the number of times, but above that my code can no longer read

def repeatedString(s, n):
    n_repetidos = n // len(s) + 1
    string_repetida = s * n_repetidos
    string_repetida_ate_n = string_repetida[:n]
    x = string_repetida_ate_n.count('a')
    return x

print(repeatedString('a', 1000000000000))

Another example, if I have a string "tab" of range 10, the string with 10 letters is "abaabaabaa", and I have the occurrence of 7 letters 'a'.

Answer 1

string_repetida = s * n_repetidos

On this line you are creating a new string that will be the string s repeated n_repetidos. There’s no point in doing that, because if the idea is just to count the number of occurrences, you can count occurrences in s and then multiply by n_repetidos. As commented, there is no reason to keep this entire string in memory.

By calculating how many times the string has repeated itself completely and how many partial characters of it have been used to complete the final string, you can sum the occurrences quite simply:

def repetir(s: str, n: int):
    # Verifica quantas vezes a string se repetiu por completo
    # E quantos caracteres foram usados para completar o total
    repetiu, sobrou = divmod(n, len(s))

    # Soma a quantidade de ocorrências em s vezes a quantidade que ela se repete
    # Mais a quantidade de ocorrências da string parcial
    return s.count('a') * repetiu + s[:sobrou].count('a')

To repetir('aba', 10), the value of repetiu would be 3, because the string 'aba' was repeated 3x in full, while sobrou would be 1, as it was used 1 character 'aba' to complete the 10 characters requested. In 'aba' the letter 'a' appears twice, so if the word repeats 3 times, 2*3 = 6, plus the occurrences in the partial string, 'a', which is once. Thus, 6+1 = 7.

Answer 2

In doing string_repetida = s * n_repetidos you are creating a string with 1 trillion characters (that is, if each character occupies 1 byte, you will need 1 terabyte for this string, so it gives error in your test as it is bursting the memory).

But anyway, you don’t have to build a giant string and then count.

An alternative to the another answer is to use the module itertools:

from itertools import islice, cycle
 
def repeatedString(s, n):
    qtd = 0
    for letra in islice(cycle(s), n):
        if letra == "a":
            qtd += 1
    return qtd
 
print(repeatedString('aba', 10)) # 7
print(repeatedString('baa', 10)) # 6

First, cycle(s) creates an iterator that iterates repeatedly through the string. As it creates an infinite iterator, I use islice to limit it to only the first n elements.

Then, just count how many are equal to "a" and return the result.

---

Only this solution is more inefficient than the other answer, especially if the n is very large (since it needs to iterate through the loop n times, while the other answer only does a few simple calculations and iterates through the string only to do the count).

Another alternative is instead to use count 2 times (once in the whole string and once in the substring), make a single loop that counts everything at once:

def repeatedString(s, n):
    repetiu, sobrou = divmod(n, len(s))
    qtd = 0

    for i, c in enumerate(s):
        if c == 'a':
            qtd += repetiu
            if i < sobrou:
                qtd += 1
    return qtd

The idea is similar to the other answer: we see how many times the string will be repeated completely, and how much more to complete the size n.

Then we iterate through her characters and indexes at the same time (using enumerate for this), and each time we find a letter "a", we already add the amount of times the string repeats itself completely. Then we see if you still need to add one more, if we are in a position that is used for the "leftover".