how to manipulate very long string to avoid out of memory with golang

Question

I trying for personal skills improvement to solve the hacker rank challenge:

There is a string, s, of lowercase English letters that is repeated infinitely many times. Given an integer, n, find and print the number of letter a's in the first n letters of the infinite string.

1<=s<=100 && 1<=n<=10^12

Very naively I though this code will be fine:

fs := strings.Repeat(s, int(n)) // full string
ss := fs[:n]                    // sub string
fmt.Println(strings.Count(ss, "a"))

Obviously I explode the memory and got an: "out of memory".

I never faced this kind of issue, and I'm clueless on how to handle it. How can I manipulate very long string to avoid out of memory ?

Answer 1

I hope this helps, you don't have to actually count by running through the string. That is the naive approach. You need to use some basic arithmetic to get the answer without running out of memory, I hope the comments help.

var answer int64

// 1st figure out how many a's are present in s.
aCount := int64(strings.Count(s, "a"))

// How many times will s repeat in its entirety if it had to be of length n
repeats := n / int64(len(s))
remainder := n % int64(len(s))

// If n/len(s) is not perfectly divisible, it means there has to be a remainder, check if that's the case.
// If s is of length 5 and the value of n = 22, then the first 2 characters of s would repeat an extra time.
if remainder > 0{
aCountInRemainder := strings.Count(s[:remainder], "a")
answer = int64((aCount * repeats) + int64(aCountInRemainder))
} else{ 
answer = int64((aCount * repeats))
}
 
return answer

There might be other methods but this is what came to my mind.