如何找出没有重复字符的最长子串？

banq
Leetcode ：给定一个字符串，找出最长的不包含重复字符的子串的长度。
思路：在这篇文章中，我们使用2个指针（滑动窗口）来解决这个问题。这个问题很好地介绍了解决leetcode问题的滑动窗口策略。

解决方案

  • 由于我们需要找到一个不包含重复字符的子字符串，因此立即想到的是列出所有子字符串。因此，在“abcabcbb”的情况下，我们将找到并列出所有可能的子字符串组合，[“a”，“ab”，“abc”，“abca”，“abcab”..]
  • 现在，一旦我们有了所有组合，我们就可以删除所有包含重复字符的字符串，并返回剩余字符串的最大长度。
  • 现在这种方法存在一些问题，首先逻辑上很复杂，其次形成组合然后搜索字符串中是否存在重复字符会增加时间复杂度。 
psuedocode
1. find all the substring of input string. TC = O(N^2) , SC = O(N)
2. find repeacting character in substring and do that for all the substring.
    TC = O(N2), SC = O(N)
  • 我们可以做得更好吗？如果您之前学习过 2-2 指针方法，那么使用它会很有意义。如果您还没有，请不要担心，我们将从解决方案中学习，以便我们可以识别并使用下一个问题。
  • 在两个指针中，我们有一个左指针和一个右指针。这2个指针基本上驱动滑动窗口。通常有一个终止条件，我们必须调整窗口。
  • 例如字符串“abcabcbb”，我们将左指针保留在索引 0 处，并将右指针移动到 b。我们还需要知道这个字符是否重复。为此，我们可以保留一个 Set 数据结构，它将在 o(1) 时间内提供更快的查找。由于堆栈不包含 b，因此我们向堆栈添加一个字符。我们这样做直到在堆栈中找到一个字符。
  • 一旦我们在堆栈中找到一个字符，我们就移动左指针，直到出现重复字符，因为现在我们知道这个字符是重复的，一个新的字符串总是会在该字符之后开始。
  • 我们可以继续这样，直到右边的窗口到达终点。 
  • 此逻辑中的一个特殊标注是，到目前为止，我们已将左侧的第一个字符设为重复字符。但是我们可能会遇到这样的情况：窗口的重复字符位于中间而不是窗口的开头。例如子字符串“abcb”。
  • 在“abcb”的情况下，我们需要不断移动左指针，直到到达重复字符，因为我们知道下一个没有重复字符的子字符串将位于我们在窗口中找到的重复字符之后。
  • 由于这种行为，我们必须使用 while 循环并不断从集合中删除字符，直到达到集合中没有重复字符的程度。

Java解决方案：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] strToChar = s.toCharArray();
        int leftWindow = 0;
        int result = 0;
        Set<Character> set = new HashSet<>();
        for(int rightWindow=0;rightWindow<s.length();rightWindow++){
            // delete from left window until we find repeating chars in the set
            while(set.contains(strToChar[rightWindow])){
                set.remove(strToChar[leftWindow]);
                leftWindow++;
            }
            // add string to set for repeacting char check
            set.add(strToChar[rightWindow]);
            // keep updating the window as we see new length in sliding window
            result = Math.max(result, (rightWindow - leftWindow)+1);
        }
 
        return result;
    }
}

Ruby解决方案

<strong>@param {String} s</strong>
<strong>@return {Integer}</strong>
def length_of_longest_substring(s)
    l = 0
    charSet = Set.new
    res = 0
    s.each_char.with_index do |c, i|
      while charSet.include?(c)
        charSet.delete(s[l])
        l=l+1
      end
      charSet.add(c);
      res = [res, (i-l)+1].max
    end
    res
end


复杂

  • 时间复杂度： O(N) 由于在滑动窗口中两个指针都没有向后移动，因此窗口向前移动，指针可以移动 O(N) 步。
  • 空间复杂度： O(N)，因为当没有重复字符且结果是整个字符串时，Set 可以包含 N 个字符。