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