Algorithem_Depth-First Search

2022-04-19

Algorithem_Depth-First Search

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

1
2
3

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法一

这道题的题目刚开始仔细看，看下面的例子1和2，以为要找的是重复字符串的长度，再后来以为是不重复字符串的长度，最后才看明白，要找的是，最长的子字符串里不包含有重复字符的长度。

题目看懂之后，想到的解法是最直观的，从左到右开始遍历字符串，设定一个默认长度1，然后依次往后取，如果取到的元素和包含在前面的元素中，则停止取，获取前面已经取到的元素的长度，然后遍历下一个字符串。可以想成，从第一个字符开始，有一个框框，框框的长度的从0开始慢慢增加，如果要增加的元素包含在框框中，则停止增加，获取先有框框的长度；然后遍历下一个字符，框框继续从1开始。


比如：
Input: s = "abcabcbb"

[a, b, c, a, b, c, b, b]

遍历：

第一个字符 a开始
框框长度0，当前元素 a，不在框框数组中，加入到框框数组里，框框长度+1
框框长度1，当前元素 b，不在框框数组中，加入到框框数组里，框框长度+1
框框长度2，当前元素 c，不在框框数组中，加入到框框数组里，框框长度+1
框框长度3，当前元素 a，包在框框数组中，框框停止增加，获取当前框框长度；然后遍历下一个字符

第二个字符 b
框框长度0，当前元素 b，不在框框数组中，加入到框框数组里，框框长度+1
框框长度1，当前元素 c，不在框框数组中，加入到框框数组里，框框长度+1
框框长度2，当前元素 a，不在框框数组中，加入到框框数组里，框框长度+1
框框长度3，当前元素 b，包在框框数组中，框框停止增加，获取当前框框长度 和上次获取到的比较大小，保存最大的；然后遍历下一个字符

...
依次类推

代码如下：


class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.length == 0 {
            return 0
        }
        
        let charList = Array(s)
        
        var maxLength = 1
        var savedList:[Character] = []
        for i in 0..<charList.count {
            var subLength = 0
            var nextE = false
            while !nextE {
                if i + subLength >= charList.count {
                    maxLength = max(maxLength, savedList.count)
                    break
                }
                if savedList.contains(charList[i+subLength]) {
                    // 说明重复了
                    maxLength = max(maxLength, savedList.count)
                    savedList = []
                    subLength = 0
                    nextE = true
                }
                else {
                    savedList.append(charList[i+subLength])
                    subLength += 1
                    nextE = false
                }
            }            
        }
        return maxLength
    }
}

但这个效率有点低，嗯，是否可以优化一下
优化点：

获取到最长的元素之后，遍历到 count-maxLength 的元素的时候，其实就可以不用遍历了，因为从这个元素开始，最长也就是 maxLength 了。
获取到最长的元素之后，后续元素的遍历，框框的长度可以以 maxlength 为准，只考虑比maxlength大的情况。

1，添加判断后，执行时间比不加判断多了65ms，而内存大小一致；
2，如果后续直接已框框的长度为准的话，还要判断框框里面的元素是有重复，会更费时。

那到底要怎么优化呢？

解法二

解法二和解法一的不同在于，解法一遇到重复字符之后，就继续遍历下一个，并且把框置为0从头开始；而解法二是遇到重复字符之后，遍历移除框最左边的元素，直到没有和要添加的元素重复为止，然后继续框向后遍历


比如：
Input: s = "abcabcbb"

[a, b, c, a, b, c, b, b]

遍历：

定义left 和 right，right 表示当前遍历进度，left 表示框框长度，数组 list 存储遍历过的字符

right=0，开始
当前元素 a，不在list数组中，加入到list数组里，right 向后
当前元素 b，不在list数组中，加入到list数组里，right 向后
当前元素 c，不在list数组中，加入到list数组里，right 向后
当前元素 a，在list数组中，left+1，list 数组最左侧元素弹出，变为[b, c]，判断 list 不包含 a，添加 a，right向后

...
依次类推

注意下面这里的逻辑：
到list 中为[a, b, c]，下一个元素为 b 时，list 中包含b，所以 left+1，list 最左侧弹出，变为[b, c]，判断后还是包含 b，所以继续 left + 1，list 最左侧弹出，变为[c]，再判断，不包含 b，添加 b，right 向后

这里的过程可参考Longest Substring Without Repeating Characters - Leetcode 3 - Python

代码如下：


class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.length == 0 {
            return 0
        }
        
        let charList = Array(s)
        var list: [Character] = []
        
        var left: Int = 0
        var maxLength: Int = 0
        
        for right in 0..<charList.count {
            let charItem = charList[right]
            while list.contains(charItem) {
                list.remove(at: 0)
                left += 1
            }
            list.append(charItem)
            maxLength = max(maxLength, right - left + 1)
        }
        return maxLength
    }
}