剑指 Offer II 016-不含重复字符的最长子字符串
发表于：2021-12-03 | 分类： 中等
字数统计: 2.6k | 阅读时长: 13分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/wtcaE1

中文题目

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

 

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

 

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

 

注意：本题与主站 3 题相同： https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

通过代码

高赞题解

我们从暴力解法开始，一步一步来优化！！！

1. 暴力解法及其缺点

请看视频：

10_03_暴力解法及其缺点.mp4

代码如下：

[]
// 1. 暴力解法：遍历数组的所有的区间，然后找到最长没有重复字符的区间
// 时间复杂度：O(n^3)
// 空间复杂度：O(n)
// 会超时
public int lengthOfLongestSubstring1(String s) {
    int n = s.length();
    if (n <= 1) return n;
    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (allUnique(s, i, j)) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }

    return maxLen;
}

private boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i <= end; i++) {
        if (set.contains(s.charAt(i))) {
            return false;
        }
        set.add(s.charAt(i));
    }
    return true;
}
[]
// 1. 暴力解法：遍历数组的所有的区间，然后找到最长没有重复字符的区间
// 时间复杂度：O(n^3)
// 空间复杂度：O(n)
// 会超时
func lengthOfLongestSubstring1(s string) int {
    var n = len(s)
    if n <= 1 {
        return n
    }
    var maxLen = 1
    for i := range s {
        for j := i + 1; j < n; j++ {
            if allUnique(s, i, j) && j - i + 1 > maxLen {
                maxLen = j - i + 1
            }
        }
    }
    return maxLen
}

func allUnique(s string, start int, end int) bool {
    var set = make(map[byte]bool)
    for i := start; i <= end; i++ {
        if set[s[i]] {
            return false
        }
        set[s[i]] = true
    }
    return true
}

2. 优化 - 滑动窗口思路

暴力解法存在重复计算，同一个子串会进行多次判断是否存在重复字符

我们可以做如下的优化：

  • 如果 s[i, j) 子串没有重复字符的话，那么如果要判断 s[i, j] 没有重复字符的话，我们只需要判断 s[i, j) 中是否存在 s[j] 即可

请看视频：
11_03_滑动窗口思路.mp4

3. 滑动窗口代码实现

请看视频：
12_03_滑动窗口代码实现.mp4

代码如下：

[]
// 2. 滑动窗口
// 时间复杂度：O(2n) = O(n)，最坏的情况是 left 和 right 都遍历了一遍字符串
// 空间复杂度：O(n)
public int lengthOfLongestSubstring2(String s) {
    int n = s.length();
    if (n <= 1) return n;
    int maxLen = 1;

    int left = 0, right = 0;
    Set<Character> window = new HashSet<>();
    while (right < n) {
        char rightChar = s.charAt(right);
        while (window.contains(rightChar)) {
            window.remove(s.charAt(left));
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
        window.add(rightChar);
        right++;
    }

    return maxLen;
}
[]
// 2. 滑动窗口
// 时间复杂度：O(2n) = O(n)，最坏的情况是 left 和 right 都遍历了一遍字符串
// 空间复杂度：O(n)
int lengthOfLongestSubstring1(string s) {
    int n = s.length();
    if (n <= 1) return n;

    int maxLen = 0;
    int left = 0, right = 0;
    unordered_set<char> window;
    while (right < n) {
        char currChar = s[right];
        if (!window.count(currChar)) {
            maxLen = max(maxLen, right - left + 1);
            window.insert(currChar);
            right++;
        } else {
            window.erase(s[left]);
            left++;
        }
    }
    return maxLen;
}
[]
# 2. 滑动窗口
# 时间复杂度：O(2n) = O(n)，最坏的情况是 left 和 right 都遍历了一遍字符串
# 空间复杂度：O(n)
def lengthOfLongestSubstring1(self, s: str) -> int:
    n = len(s)
    if n <= 1: return n
    max_len, window = 0, set()
    left = right = 0
    while right < n:
        if s[right] not in window:
            max_len = max(max_len, right - left + 1)
            window.add(s[right])
            right += 1
        else:
            window.remove(s[left])
            left += 1
    return max_len
[]
// 2. 滑动窗口
// 时间复杂度：O(2n) = O(n)，最坏的情况是 left 和 right 都遍历了一遍字符串
// 空间复杂度：O(n)
var lengthOfLongestSubstring1 = function(s) {
    const n = s.length
    if (n <= 1) return n

    let left = 0, right = 0
    const window = new Set()
    let maxLen = 0
    while (right < n) {
        if (!window.has(s[right])) {
            maxLen = Math.max(maxLen, right - left + 1)
            window.add(s[right])
            right++
        } else {
            window.delete(s[left])
            left++
        }
    }
    return maxLen
};
[]
// 2. 滑动窗口
// 时间复杂度：O(2n) = O(n)，最坏的情况是 left 和 right 都遍历了一遍字符串
// 空间复杂度：O(n)
func lengthOfLongestSubstring2(s string) int {
    var n = len(s)
    if n <= 1 {
        return n
    }
    var maxLen = 1
    var left, right, window = 0, 0, make(map[byte]bool)
    for right < n {
        var rightChar = s[right]
        for window[rightChar] {
            delete(window, s[left])
            left++
        }
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
        window[rightChar] = true
        right++
    }
    return maxLen
}

4. 我们再来优化

以上当在窗口中存在重复字符，是一个一个字符的缩小窗口~

我们可以通过记住每个字符在字符串中的索引，当遇到重复字符的时候，就可以直接跳到重复字符的后面

请看视频：
13_03_滑动窗口性能优化.mp4

代码如下：

[]
// 3. 优化后的滑动窗口
// 时间复杂度：O(n)
// 空间复杂度：O(n)
public int lengthOfLongestSubstring3(String s) {
    int n = s.length();
    if (n <= 1) return n;
    int maxLen = 1;

    int left = 0, right = 0;
    Map<Character, Integer> window = new HashMap<>();
    while (right < n) {
        char rightChar = s.charAt(right);
        int rightCharIndex = window.getOrDefault(rightChar, 0);
        left = Math.max(left, rightCharIndex);
        maxLen = Math.max(maxLen, right - left + 1);
        window.put(rightChar, right + 1);
        right++;
    }

    return maxLen;
}
[]
// 哈希映射
int lengthOfLongestSubstring2(string s) {
    int n = s.length();
    if (n <= 1) return n;

    int maxLen = 0;
    int left = 0, right = 0;
    // 存储窗口中每个字符及其位置的下一个位置
    // 表示如果再次碰到这个字符的时候，那么 left 就跳到这个字符所在位置的下一个位置
    unordered_map<char, int> window;
    while (right < n) {
        char currChar = s[right];
        unordered_map<char, int>::iterator it = window.find(currChar);
        int currCharIndex = (it == window.end() ? -1 : it->second);
        left = max(left, currCharIndex);
        maxLen = max(maxLen, right - left + 1);

        window[currChar] = right + 1;
        right++;
    }
    return maxLen;
}
[]
# 哈希映射
def lengthOfLongestSubstring2(self, s: str) -> int:
    n = len(s)
    if n <= 1: return n
    max_len, window = 0, {}
    left = right = 0
    while right < n:
        right_char_index = window.get(s[right], -1)
        left = max(left, right_char_index)
        max_len = max(max_len, right - left + 1)
        window[s[right]] = right + 1
        right += 1
    return max_len
[]
// 哈希映射
var lengthOfLongestSubstring2 = function(s) {
    const n = s.length
    if (n <= 1) return n

    let left = 0, right = 0
    const window = new Map()
    let maxLen = 0
    while (right < n) {
        const rightCharIndex = window.has(s[right]) ? window.get(s[right]) : -1
        left = Math.max(left, rightCharIndex)
        maxLen = Math.max(maxLen, right - left + 1)
        window.set(s[right], right + 1)
        right++
    }
    return maxLen
};
[]
// 3. 优化后的滑动窗口
// 时间复杂度：O(n)
// 空间复杂度：O(n)
func lengthOfLongestSubstring3(s string) int {
    var n = len(s)
    if n <= 1 {
        return n
    }
    var maxLen = 1
    var left, right, window = 0, 0, make(map[byte]int)
    for right < n {
        var rightChar = s[right]
        var rightCharIndex = 0
        if _, ok := window[rightChar]; ok {
            rightCharIndex = window[rightChar]
        }
        if rightCharIndex > left {
            left = rightCharIndex
        }
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
        window[rightChar] = right + 1
        right++
    }
    return maxLen
}

5. 追求极致性能

请看视频：
...03_使用数组代替HashMap.mp4

代码如下：

[]
// 4. 追求程序的极致性能
// s 由英文字母、数字、符号和空格组成
public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    if (n <= 1) return n;
    int maxLen = 1;

    int left = 0, right = 0;
    int[] window = new int[128];
    while (right < n) {
        char rightChar = s.charAt(right);
        int rightCharIndex = window[rightChar];
        left = Math.max(left, rightCharIndex);
        maxLen = Math.max(maxLen, right - left + 1);
        window[rightChar] = right + 1;
        right++;
    }

    return maxLen;
}
[]
// 字符数组
int lengthOfLongestSubstring(string s) {
    int n = s.length();
    if (n <= 1) return n;

    int maxLen = 0;
    int left = 0, right = 0;
    vector<int> window(128, 0);
    while (right < n) {
        char currChar = s[right];
        int currCharIndex = window[currChar];
        left = max(left, currCharIndex);
        maxLen = max(maxLen, right - left + 1);

        window[currChar] = right + 1;
        right++;
    }
    return maxLen;
}
[]
# 字符数组
def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
    if n <= 1: return n
    max_len, window = 0, [0]*128
    left = right = 0
    while right < n:
        right_char_index = window[ord(s[right])]
        left = max(left, right_char_index)
        max_len = max(max_len, right - left + 1)
        window[ord(s[right])] = right + 1
        right += 1
    return max_len
[]
// 字符数组
var lengthOfLongestSubstring = function(s) {
    const n = s.length
    if (n <= 1) return n

    let left = 0, right = 0
    const window = new Array(128).fill(0)
    let maxLen = 0
    while (right < n) {
        const rightCharIndex = window[s[right].charCodeAt()]
        left = Math.max(left, rightCharIndex)
        maxLen = Math.max(maxLen, right - left + 1)
        window[s[right].charCodeAt()] = right + 1
        right++
    }
    return maxLen
};
[]
// 4. 追求程序的极致性能
// s 由英文字母、数字、符号和空格组成
func lengthOfLongestSubstring(s string) int {
    var n = len(s)
    if n <= 1 {
        return n
    }
    var maxLen = 1
    var left, right, window = 0, 0, [128]int{}
    for right < n {
        var rightChar = s[right]
        var rightCharIndex = window[rightChar]
        if rightCharIndex > left {
            left = rightCharIndex
        }
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
        window[rightChar] = right + 1
        right++
    }
    return maxLen
}

在刷题的时候：

  1. 如果你觉得自己数据结构与算法基础不够扎实，那么请点这里，这里包含了一个程序员 5 年内需要的所有算法知识

  2. 如果你感觉刷题太慢，或者感觉很困难，或者赶时间，那么请点这里。这里用 365 道高频算法题，带你融会贯通算法知识，做到以不变应万变

  3. 回溯、贪心和动态规划，是算法面试中的三大难点内容，如果你只是想搞懂这三大难点内容 请点这里

以上三个链接中的内容，都支持 Java/C++/Python/js/go 五种语言

统计信息

通过次数 提交次数 AC比率
7653 15692 48.8%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
字符串 哈希表 滑动窗口
上一篇:
剑指 Offer II 015-字符串中的所有变位词
下一篇:
剑指 Offer II 017-含有所有字符的最短字符串
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo