Revision history [back]

Here's an implementation of finding the longest substring that does not contain any repeating characters in Scala:

def longestSubstring(s: String): String = {
  var start = 0
  var end = 0
  var maxLength = 0
  var substrStart = 0
  var charMap = Map[Char, Int]()

  for (i <- 0 until s.length) {
    val c = s(i)
    if (charMap.contains(c) && charMap(c) >= start) {
      start = charMap(c) + 1
    }
    charMap += (c -> i)
    end = i
    if (end - start + 1 > maxLength) {
      maxLength = end - start + 1
      substrStart = start
    }
  }

  s.substring(substrStart, substrStart + maxLength)
}

The main algorithm is based on the sliding window technique, where we maintain a "window" of unique characters as we scan the input string from left to right. We use a mapping from characters to their indices in the string to keep track of the last occurrence of each character in the window. When we encounter a repeated character, we move the starting point of the window to the index after the last occurrence of that character.

We also keep track of the starting index and length of the longest substring seen so far. When the window is updated, we compare the length of the current window to the longest seen so far, and update the longest substring if necessary.

Finally, we return the longest substring by using the substring method on the original input string based on the starting index and length of the longest substring.