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

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
}


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')

• I have considered your suggestions and updated question accordingly. And thank you for the solution it is expressive(self explanatory). Jul 16, 2019 at 21:38

(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.)

• 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. Jul 16, 2019 at 4:33
• @Sandio Thanks for the info. Jul 16, 2019 at 8:11