LeetCode / Scala - 无重复字符最长子串 ，最长回文子串

一.引言

LeetCode 里有一类字符子串问题，这里主要分析无重复字符的最长子串与最长回文子串，总结相关方法。

二.无重复字符最长子串

1.题目要求

 给定字符串 s，要求找出字符内无重复的最长子串，注意是子串不是子序列。

2.滑动指针法

A.思路分析

通过 start 与 end 双指针指定最长子串范围，通过 HashMap 记录每一个 char 字符的索引并实现去重。

-> 遍历字符串所有 char 字符

-> 判断当前字符是否在 HashMap 中，并更新当前 start

-> end += 1，并记录当前 char 对应的索引

-> length = end - start，比较 length 与 maxLength 并更新最大长度

B.代码实现

  def solution(s: String): Int = {
 
    // 双指针与索引Map
    var maxLength = 0
    var start = 0
    var end = 0
 
    val indexMap = mutable.HashMap[Char, Int]()
 
    // 转换为char
    val arr = s.toCharArray
 
    s.toCharArray.foreach(char => {
      if (indexMap.contains(char)) {
        start = math.max(indexMap(char), start) // 更新 start
      }
      end += 1 // 更新 end
      indexMap(char) = end
      maxLength = math.max(end - start, maxLength) // 更新 maxLength
      println(s"char: $char start: $start end: $end max: $maxLength arr: ${s.slice(start, end).mkString("")}")
    })
 
    maxLength
  }

为了直观，我们加入了日志打印，以 s = "abba" 为例进行测试：

  def main(args: Array[String]): Unit = {
    val s = "abba"
    println(solution(s))
  }

可以结合执行过程理解双指针 start 和 end 的变化。 

C.执行效率

时间复杂度 O(n)，其中 n 为字符串的长度，即 char 的数量，空间复杂度为 O(|∑|)，其中 ∑ 为当前字符串的去重集合，正常情况可以近似为 O(n)，极端情况例如 s="11111" 则退化为 O(1)。

三.最长回文子串

1.题目要求

给定字符串 s，寻找其最长回文子串，这里解释下什么是回文串，即正反一样的字符串，例如 aabbaa，aba，ccccc 均为回文子串，注意最长无重复子串返回字符串长度而本例返回字符串。

2.中心扩展法

A.思路分析

首先清晰回文字符的转移条件，假设 P(i，j) 为回文子串，如果 i-1，j+1 对应位置元素相同，则 P(i-1, j+1) 也是回文子串，如此类推。

-> 初始化 maxLeft，maxRight 记录最长回文串的区间，初始化 maxLength 记录最长长度

-> 遍历数组数组索引，向左侧探索，当前索引为 mid，则左侧为 mid - 1，如果 s(mid) = s(left) 则 P(left, mid) 构成回文子串，left -=1 继续向左探索 

-> 向右侧探索，方法同上，right = mid + 1，判断 s(mid) 与 s(right)

-> 向两侧扩展，单向扩展主要寻找与 mid 元素相同的元素，例如 a -> aaa，双侧则主要是寻找两侧相同元素，例如 aaa -> baaab，判断 s(left) = s(right)

-> 更新 maxLeft，maxRight 记录当前最长回文串范围

B.代码实现

  // 中心扩展算法
  def solution(s: String): String = {
 
    var length = 1
    // 从每个 mid 开始向两边扩散
    var maxLeft = 0 // 起点
    var maxRight = 0 // 终点
    var maxLength = 0 // 最长回文串长度
 
    val arr = s.toCharArray
 
    arr.indices.foreach(mid => {
 
      var left = mid - 1
      var right = mid + 1
 
      // 向左侧扩展
      while (left >= 0 && arr(left).equals(arr(mid))) {
        left -= 1
        length += 1
      }
 
      // 向右侧扩展
      while (right <= arr.length - 1 && arr(right) == arr(mid)) {
        right += 1
        length += 1
      }
 
      // 向两侧扩展
      while (left >= 0 && right <= arr.length - 1 && arr(left) == arr(right)) {
        left -= 1
        right += 1
        length += 2
      }
 
      // 更新
      if (length > maxLength) {
        maxLeft = left
        maxRight = right
        maxLength = length
      }
 
      length = 1
    })
 
    println(maxLeft, maxRight, maxLength)
 
    s.substring(maxLeft + 1, maxRight)
  }

分别向左，右，两侧扩展，最后更新区间，可以参照上面思路分析，由于判断相等后，继续 left -= 1 寻找下一个 left，所以最后满足的左边界为 realLeft = maxLeft + 1，maxRight 同理，maxRight = realRight + 1，所以最终结果 subString(maxLeft + 1，maxRight)。

C.执行效率

欧了一把，不知道这次提交怎么跑这么快，算法时间复杂度 O(n^2)，因为遍历 n 个字符，每个字符左右扩展，空间复杂度 O(1)。

四.总结

可以看到很多算法都使用了 双指针、HashMap，因此要理解它们常用的用法与边界条件，其次回文串由于 P(i，j) 向 P(i-1，j+1) 的转移状态，也适用于动态规划，后面有时间整理一下动态规划相关。