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
}

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

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