Scala实现最长无重复子串：求更简洁的Sliding Window优化方案

原问题及实现 #

我已使用Sliding Window技术解决了LeetCode上的Longest Substring Without Repeating Characters问题，Scala实现代码如下：

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
}

该方案已通过测试，但因索引处理和内部函数的存在显得稍显繁琐，能否提供更简洁的Scala实现方案？

更简洁的实现方案 #

def lengthOfLongestSubstring(s: String): Int = {
  s.zipWithIndex.foldLeft((Map.empty[Char, Int], 0, 0)) {
    case ((charIndexMap, leftBound, maxLength), (currentChar, rightIndex)) =>
      // 计算新左边界：若当前字符已存在，左边界移至其上次出现位置的下一位，否则保持原边界
      val newLeft = math.max(leftBound, charIndexMap.getOrElse(currentChar, -1) + 1)
      // 更新当前字符的最新索引
      val updatedMap = charIndexMap + (currentChar -> rightIndex)
      // 计算当前窗口长度并更新最大长度
      val newMax = math.max(maxLength, rightIndex - newLeft + 1)
      (updatedMap, newLeft, newMax)
  }._3 // 最终返回记录的最大长度
}

优化说明 #

• 用foldLeft替代scanLeft：直接在迭代中维护状态，避免生成所有中间实例后再取最大值，空间和时间效率更优
• 移除递归边界逻辑：通过Map记录字符最新索引，直接计算左边界位置，省去繁琐的递归内部函数
• 简化状态载体：用三元组替代自定义Acc类，减少冗余代码，逻辑更紧凑
• 保持函数式风格：使用不可变Map，全程无副作用，契合Scala函数式编程习惯

内容的提问来源于stack exchange，提问作者Michael