"Longest Substring Without Repeating Characters" in Scala

Question

I've solved Longest Substring Without Repeating Characters problem using sliding window technique :

def lengthOfLongestSubstring(s: String): Int = {

  case class Acc(chars: Set[Char], left: Int, len: Int)
  s.zipWithIndex.scanLeft(Acc(Set(), 0, 0)) { case (acc, (c, right)) =>

    def moveLeftBoundary(chars: Set[Char], left: Int): (Set[Char], Int) =
      if (chars.contains(c)) moveLeftBoundary(chars - s(left), left + 1) else (chars, left)

    val (chars, left) = moveLeftBoundary(acc.chars, acc.left)
    Acc(chars + c, left, right - left + 1)

  }.map(_.len).max
}

The solution is accepted and not very long but looks a bit clumsy because of indices and the internal function. Could you suggest a simpler solution in Scala ?

Answer 1

I don't care fp or not for performance sensitive codes. Actually pure fp style code is always slower than no pure fp code in my experience.

Here we go:

def lengthOfLongestSubstring(s: String): Int = {
    def rec(start: Int, end: Int, size: Int, visited: Array[Int]): Int = 
        if (end >= s.length) size
        else {
            val newStart = start.max(visited(s(end).toInt) + 1)
            visited(s(end).toInt) = end
            rec(newStart, end+1, size.max(end-newStart+1), visited)
        }

    rec(0, 0, 0, Array.fill(128)(-1))
}