Need help in solving the special string Again problem "the scala way"

Question
16

Here’s my approach. I didn’t run it in Hackerank so I don’t know it passes everything but it does pass the sample inputs.

Ideas behind this:

  • Everything relates to a subsequence of the input, so no need to allocate a bunch of intermediate data structures and substrings, just move a cursor through the input
  • The first type of special string is a contributor to the second type, so you can use the results of that calculation while determining the contribution of the second and basically do both at the same time
  • Once a run of characters is accounted for as the first type of special string, it doesn’t need to be visited again, so the cursor only advances and makes this roughly O(n)
  • Scala is multi-paradigm, so “the Scala way” depends heavily on the author, and I embrace the form that allows limited local mutability and doesn’t require everything use functional combinators
def substrCount(n: Int, s: String): Long = {
  val end = n

  def count(start: Int, expect: Char): Int = {
    var c = 0
    var idx = start
    while(idx < end && s.charAt(idx) == expect) { c += 1; idx += 1 }
    c
  }

  def sumSeries(i: Int): Long = (i * (i + 1)) >> 1

  @scala.annotation.tailrec
  def specials(prefixStart: Int, total: Long): Long = {
    if (prefixStart < end) {
      val c = s.charAt(prefixStart)
      val prefixLen = count(prefixStart, c)
      val prefixEnd = prefixStart + prefixLen
      val suffixStart = prefixEnd + 1
      val suffixLen = count(suffixStart, c)

      val contrib = sumSeries(prefixLen) + prefixLen.min(suffixLen)
      specials(prefixEnd, total + contrib)
    } else {
      total
    }
  }

  specials(0, 0L)
}

It should be plenty quick even on the large inputs, and can be made quicker still since some portions of the input are visited an extra time or two unnecessarily. Essentially, the “suffix” part of a type-2 special string is itself a type-1 special string, and might be the start of its own type-2 special string. Accounting for this incrementally was starting to make the implementation feel complicated and I opted for simplicity. But it should be possible and if you can do it then it’d be nearly as fast as Scala would get since without the extra data structures and each character visited only once in order it would be quite cpu- and memory-friendly.

1 Like