LeetCode(3)Longest Substring Without Repeating Characters

题目

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

翻译一下就是：给定一个字符串，找到最长不重复字符串的长度

例如：给定“pwwkew”,答案是“wke”，长度是3，而不是“pwke”，因为“pwke”是子序列，而不是子字符串

思路

最直接能够想到的方法，遍历所有的子字符串，写一个方法，如果这个子字符串中没有重复的字符，那么返回true，记录这个字符串的长度，随时更新

找到所有的子字符串就需要两层循环，时间复杂度就是O（n^2），时间复杂度有些高

代码

public class method1 {
    public int lengthOfLongestSubstring(String s){
        int n=s.length();
        int ans=0;
         for (int i = 0; i < n; i++)
                for (int j = i + 1; j <= n; j++)
                    if (allUnique(s, i, j)) 
                        ans = Math.max(ans, j - i);
            return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) 
                return false;
            set.add(ch);
        }
        return true;
    }
}

思路优化

所以，解决方案中给出了一种滑动窗口的方法

滑动窗口是数组和字符串问题中常用的抽象概念。窗口是数组/字符串中通常由开始和结束索引定义的一系列元素，即 [i，j）（左闭合，右开放）。

    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

滑动过程，如下图所示：