Count character 'a' in first n characters of indefinitely repeating string s

Question

Problem statement:

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

For example, if the string s = 'abcac' and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of a in the substring.

Function Description

Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a in the prefix of length n in the infinitely repeating string.

repeatedString has the following parameter(s):

s: a string to repeat
n: the number of characters to consider

Input Format The first line contains a single string, s. The second line contains an integer, n.

Output Format

Print a single integer denoting the number of letter a's in the first letters of the infinite string created by repeating infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0 The first letters of the infinite string are abaabaabaa. Because there are a's, we print on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1 Because all of the first letters of the infinite string are a, we print on a new line.

My Solution:

def repeatedString(s: String, n: Long): Long = {
 def getCount(str: String): Int = str.groupBy(identity).get('a').map(x => x.length).getOrElse(0)
 val length= s.length
 val duplicate: Long = n / length
 val margin = n % length
 val numberOccurencesInString = getCount(s)
 val countInRepetetiveString = numberOccurencesInString * duplicate
 val numberOfOccurencesInStripedString = getCount(s.take(margin.toInt))
 countInRepetetiveString + numberOfOccurencesInStripedString
}

• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! Please see What to do when someone answers. I have rolled back Rev 3 → 2

Answer 1

Your getCount() method is a little difficult to read, on one long line like that, and way too complicated. s.count(_ == 'a') is both concise and efficient.

It's not clear why the number of s repetitions possible in n is called duplicate. It seems an odd choice for that variable name.

Your algorithm is sound, I just find it excessively verbose, especially for a language that prides itself on being both expressive and concise.

val sLen = s.length
s.count(_ == 'a') * (n/sLen) + s.take((n%sLen).toInt).count(_ == 'a')

• Sandio: I have considered your suggestions and updated question accordingly. And thank you for the solution it is expressive(self explanatory).

Answer 2

(Disclamer: It's been quite a while that I used Scala.)

Your code is quite complicated. Scala provides the LazyList which allows to virtually repeat the string indefinitely. You then just need to "take" the n first characters, filter out the as and count them:

def repeatedString(s: String, n: Int) =
 LazyList.continually(s).flatten.take(n).filter(_ == 'a').size

(Edit: Changed n to an Int. Unfortunately this solution won't work if n is a Long.)

• Sandio: take takes Int as parameter. And we are passing Long value for Int. It is giving compiler error. Even if we use n.toInt, there is a possibility of loosing precision. Try Sample Input 1.