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

示例 1:

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

示例 2:

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

示例 3:

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

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解法1

思路:使用双层循环,外层循环取字符串s的每个位置,内层循环取外层循环的值至字符串末尾。在内层循环中创建一个范围为0-255的boolean数组用来判断字符是否重复出现,这比HashMap更加轻量。最后,使用一个名为maxLen的变量存放最终结果,我们在内层循环更新这个变量。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;

        for(int i=0;i < s.length();i++) {
            boolean[] bitset = new boolean[255];
            int len = 0;

            for(int j=i;j < s.length();j++) {
                if(bitset[s.charAt(j)])
                    break;
                bitset[s.charAt(j)] = true;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }

        return maxLen;
    }
}

解法2

解法一采用了双重循环,时间复杂度是O(n^2)的,我们可以使用滑动窗口方法,维护一个[i, j),0<=i<j<=|s|的窗口,确保窗口内的字串不含重复字符。窗口的前沿是j,后沿是i。前沿滑动,直到加入到窗口内的字符出现重复。此时,我们滑动窗口后沿,直到窗口内不含重复字符。我们在窗口前沿滑动时,计算maxLen = max(maxLen, i – j). 因为是左闭右开区间,直接用i-j就是窗口的大小。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int maxLen = 0;
        boolean[] bitset = new boolean[255];
        int i = 0, j = 0; // i,j是滑动窗口的起点与终点,我们需要确保[i, j)内不存在重复字符

        while (i < s.length() && j < s.length()) {
            // 若窗口不包含字符s[j],就将其加入bitset
            if(!bitset[s.charAt(j)]){
                bitset[s.charAt(j++)] = true;
                maxLen = Math.max(maxLen, j - i);
            }else{
                // 遇到重复字符,i开始滑动,并且从bitset中剔除,直到使窗口内不包含重复字符。
                // 此分之触发是由于字符s[j] 在 s[i, j) 中存在
                // 我们不能直接将bitset清空,然后让i = j。这样做是不对的,例如"dvdf",当j指向第二个d时,我们将i=j,就会漏掉字母v。
                // 导致最长不重复的字串是"df"而不是"vdf"
                bitset[s.charAt(i++)] = false;
            }
        }

        return maxLen;
    }
}

参考:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/

pwrliang Algorithms, Sliding Window, String

Leave a Reply

Your email address will not be published. Required fields are marked *