Understanding repetition count in a Python String

Question

I have this challenge: Repeated String to solve. I have been trying to solve the challenge but getting failure cos of Memory Failure. I cannot help this situation cos the HackerRank platform is not supporting my solution. Might be 32-bit platform.

I have this solution for this, which is quite working for problem having smaller length, but I have worked on this thing to learn according to less memory usage.

My Code:

def repeatedString(s, n):
   if(s != 'a'):
     return len([x for x in (s*n)[:n] if x == 'a'])

   return n

Now this throws Memory Error error for input having very large length, and string.

I have researched on it, and saw some submissions, and found this out.

Correct Solution from Leaderboard:

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

That's it! I got so confused by this solution that I could figure what is actually happening and how. Could anybody please let me know how the above correct solution works? I am new to python and trying my best to get my hands dirty on competitive coding. Thank You!

Answer 1

Your function is throwing a Memory error because you are constructing a string with the length of the input paramater n.

n can be 10^12, which results in a string with a maximum length 1000 billion letters, which would mean the string you are creating has a possible memory size of 1 terabyte (Possibly more depending on the encoding of your string).

So there has to be another way to count the number of a's in a string of that size right?

Yes (That's why the correct answer is different from your solution).

---

1. First we get the length of the input string.

L = len(s)

For example 'abcde' has a length of 5.

---

2. Then, we count the number of 'a's in s.

s.count('a')

---

3. Next, we want to know how many times s is repeated as a whole before we reach a string with a length of n.

(n//L)

The // operator is called integer division, which results in a whole number. For instance with s='abcde' and n=14, n//L equals 2.

---

4. Multiple the number of 'a's in s by the number of times s can fit into a string of length n.

s.count('a') * (n//L)

---

5. We are almost done, but for our example, something is still missing. 'abcde' can be repeated twice inside a string of length n, but there are still 4 characters left, in our example 'abcd'.

Here, we construct the remaining string from s with s[:n % L], or in our example s[:14 % 5] or s[:4], which results in 'abcd'.

Then we count the number of 'a's in this string with s[:n % L].count('a')

---

6. Add it all together and we get the function in your answer:

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

Answer 2

So, the key difference between the two algorithms is that in your original, you do s*n, which will actually try to build the massive string in-memory. This is why you get the memory error.

The second algorithm essentially says "For a string s of length X that's repeated out to length N, s will fit into M N//X times, possibly with a chunk of s left over (the division remainder).

E.g. if your string is aab (X=3) and N is 10, you know the string will fit 3 times, with 1 character left over.

So, given there are 2 letter a in s, you know that there will be 2*3 a in the first 9 chars. Now you need to deal with the remainder. The final character (the remainder) will be the first character of s.

In the second solution, s.count('a') * (n//L) + s[:n % L].count('a') is these two parts;

s.count('a') * (n//L) - This gives you the 2 * 3 in my example.

s[:n % L].count('a') - this gives you the 'remainder' part.