大厂高频面试真题详解:最长无重复字符的子串

简介: 大厂高频面试真题详解:最长无重复字符的子串

给定一个字符串,请找出其中无重复字符的最长子字符串。

在线评测地址:领扣题库官网

样例 1:

输入: "abcabcbb"
输出: 3
解释: 最长子串是 "abc".

样例 2:

输入: "bbbbb"
输出: 1
解释: 最长子串是 "b".

解题思路

  • 暴力解法时间复杂度较高,会达到O(n^3),故而采取滑动窗口的方法降低时间复杂度。
  • 我们使用两个指针表示字符串中的某个子串的左右边界。每步操作中,右指针向右移动一位,然后不断移动左指针,直到这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着以右指针结束的,不包含重复字符的最长子串。我们记录下这个子串的长度。
  • 在枚举结束后,我们找到的最长的子串的长度即为答案。

算法流程

  • window是滑窗内字符的集合,初始化为空。从前向后移动滑窗,同时更新当前子串长度cur_len和最长子串长度max_len。当滑窗右端移动到字符ch:

    • 如果ch已存在window中,那么从滑窗的左端起删除字符,直到删除ch。每删除一个字符cur_len减1。
    • 将ch添加到window中,cur_len加1。
    • 更新最长子串长度max_len。
  • 返回max_len。

复杂度分析

  • 时间复杂度:O(n),n为字符串s长度。左指针和右指针分别会遍历整个字符串一次。
  • 空间复杂度:O(|Σ|)。Σ为字符串s中出现的字符集。由于我们使用哈希表来存储子串的字符,因此空间复杂度为O(|Σ|)。
    代码

class Solution {

    public int lengthOfLongestSubstring(String s) {

        if (s == null) {
            return 0;
        }

        HashSet<Character> window = new HashSet<Character>();

        int left = 0, curLen = 0, maxLen = 0;
        char[] sc = s.toCharArray();

        for (char ch: sc) {

            // 从前向后删除,直到删除了ch
            while (window.contains(ch)) {

                window.remove(sc[left]);
                left ++;
                curLen --;
            }
            // 添加ch
            window.add(ch);
            curLen ++;
            // 更新长度
            maxLen = Math.max(maxLen, curLen);
        }
        return maxLen;
    }
}

更多题解参考:九章官网solution

相关文章
|
7月前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
算法 程序员
【Leetcode】NC31 第一个只出现一次的字符(牛客网)、面试题 01.01. 判定字符是否唯一
题目描述: 描述 在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
69 0
|
存储 自然语言处理 算法
ES高频面试问题:一张图带你读懂 Elasticsearch 中“正排索引(正向索引)”和“倒排索引(反向索引)”区别
ES高频面试问题:一张图带你读懂 Elasticsearch 中“正排索引(正向索引)”和“倒排索引(反向索引)”区别
ES高频面试问题:一张图带你读懂 Elasticsearch 中“正排索引(正向索引)”和“倒排索引(反向索引)”区别
|
7月前
|
算法
面试题 01.01:判定字符是否唯一
面试题 01.01:判定字符是否唯一
43 0
|
7月前
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
36 0
|
Java 数据处理
Java IO(File、字节输入输出流、字符输入输出流、打印流)附带相关面试题
1.File类,2.字节输入输出流(InputStream Outputstream),3.Writer与Reader字符输入输出流,4.打印流
91 0
|
编译器 C语言 C++
C语言面试题 - 字符空间操作类
C语言面试题 - 字符空间操作类
85 0
|
前端开发 容器
🍊Flex布局最佳实践之骰子实战篇(面试高频考点,速来围观呀~)
🍊Flex布局最佳实践之骰子实战篇(面试高频考点,速来围观呀~)
651 6
🍊Flex布局最佳实践之骰子实战篇(面试高频考点,速来围观呀~)
|
Serverless C语言 索引
华为面试C语言真题(二)
华为面试C语言真题( 二)
313 1
华为面试C语言真题(二)
|
消息中间件 NoSQL Java
高频Java面试题集锦(含答案),让你的面试之路畅通无阻!
或许这份面试题还不足以囊括所有 Java 问题,但有了它,我相信你一定不会“败”的很惨,因为有了它,足以应对目前市面上绝大部分的 Java 面试了,因为这篇文章不论是从深度还是广度上来讲,都已经囊括了非常多的知识点了。 凡事预则立,不预则废。能读到这里的人,我相信都是这个世界上的“有心人”,还是那句老话:上天不负有心人!我相信你的每一步努力,都会收获意想不到的回报。