Leetcode in Scala3 (Dotty): Repeated String Match

The solution of Repeated String Match is relatively simple:

object Solution
// time: complexity to find b_len string in a_len + b_len string
//       O(b_len * (a_len + b_len))
// space: O(a_len + b_len)
def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length
val aRepeated = a * repeatCount

if (aRepeated.contains(b))
repeatCount
else if ((aRepeated + a).contains(b))
repeatCount + 1
else
-1


The next thing I’d like to know is that if the current solution with string multiplication is slower than the one with StringBuilder. My first attempt is as follows:

import scala.annotation.tailrec

object Solution

def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length

@tailrec
def loop(sb: StringBuilder = new StringBuilder): StringBuilder =
if (sb.length >= b.length)
sb
else
loop(sb.append(a))

val sb = loop()

if (sb.contains(b))
repeatCount
else if (sb.append(a).contains(b))
repeatCount + 1
else
-1


It compiles but gives the incorrect answer. Why? You might notice that StringBuilder calls contains. It would cause a compilation error in Java because StringBuilder doesn’t have this method. The explanation is that the contains is not one that I think.

StringBuilder in Scala is derived from AbstractSeq[Char]. AbstractSeq[Char] has the polymorphic method contains defined as:

def contains[A1 >: A](elem: A1): Boolean = exists (_ == elem)


Where A is Char for a StringBuilder. If StringBuilder calls contains("a"), then the compiler infers A1 to the least common supertype of Char and String which is Any. With Any and AnyVal, such a call would never cause a compilation error with any argument given to contains:

@ val sb = new StringBuilder("abc")
sb: StringBuilder = IndexedSeq('a', 'b', 'c')

@ sb.contains("a")
res1: Boolean = false

@ sb.contains(1)
res2: Boolean = false


Moreover, the problem is well known and much broader as I found out from the community.

The funny thing is that Int is a supertype of Char, that causes

@ sb.contains(97)
res3: Boolean = true


Finally, the correct code is as follows:

import scala.annotation.tailrec

object Solution

def repeatedStringMatch(a: String, b: String): Int =
val repeatCount = (b.length + a.length - 1) / a.length

@tailrec
def loop(sb: StringBuilder = new StringBuilder): StringBuilder =
if (sb.length >= b.length)
sb
else
loop(sb.append(a))

val sb = loop()

if (sb.toString.contains(b))
repeatCount
else if (sb.append(a).toString.contains(b))
repeatCount + 1
else
-1