LeetCode-无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

• 输入: “abcabcbb”
  输出: 3
  解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

• 输入: “bbbbb”
  输出: 1
  解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

• 输入: “pwwkew”
  输出: 3
  解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

  解法

  object LongestNoneRepeatSubString {
  
       def main(args: Array[String]): Unit = {
            println(solution1("abcabcbb"))
            println(solution2("abcabcbb"))
            println(solution3("abcabcbb"))
  
  
            println(solution1("abcabcdefghabcbb"))
            println(solution2("abcabcdefghabcbb"))
            println(solution3("abcabcdefghabcbb"))
       }
  
       /**
        * 蛮力法
        */
       def solution1(str: String): Int = {
            var max: Int = 0
            for (i <- 0 until str.length) {
                 for (j <- i + 1 until str.length) {
                      if (!isRepeat(str.substring(i, j + 1))) {
                           max = Math.max(max, j - i + 1)
                      }
                 }
            }
            max
       }
  
       def isRepeat(str: String): Boolean = {
            val set = mutable.Set[Int]()
            str.chars().forEach(a => set.add(a))
            set.size != str.length
       }
  
       /**
        * O(2n)
        */
       def solution2(str: String): Int = {
            var max: Int = 0
            val set = mutable.Set[Char]()
            var i = 0
            var j = 0
            while (i < str.length && j < str.length) {
                 if (!set.contains(str.charAt(j))) {
                      set += str.charAt(j)
                      j += 1
                      max = Math.max(max, j - i)
                 } else {
                      set.remove(str.charAt(i))
                      i += 1
                 }
            }
            max
       }
  
       /**
        * O(n)
        */
       def solution3(str: String): Int = {
            var max: Int = 0
            val map = mutable.Map[Char, Int]()
            var i = 0
            var j = 0
            while (j < str.length) {
                 if (map.contains(str.charAt(j))) {
                      i = map.get(str.charAt(j)).get + 1
                      map += (str.charAt(j) -> j)
                 }
  
                 map += (str.charAt(j) -> j)
                 j += 1
                 max = Math.max(max, j - i)
            }
            max
       }
  
  }