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

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(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 ?

CodePudding user response：

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.

CodePudding user response：

As you found out, if you actually generate the string you will end up having that huge memory block in RAM.

One common way to represent a "big sequence of incoming bytes" is to implement it as an io.Reader (which you can view as a stream of bytes), and have your code run a r.Read(buff) loop.

Given the specifics of the exercise you mention (a fixed string repeated n times), the number of occurrence of a specific letter can also be computed straight from the number of occurences of that letter in s, plus something more (I'll let you figure out what multiplications and counting should be done).