题目

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

示例 1: :::info 输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 ::: 示例 2: :::info 输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 ::: 示例 3: :::info 输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 :::

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

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

解题一：

暴力破解，使用嵌套循环将新的字符判断是否已存在字符串中，如果存在则截取重复的索引之后的字符串，再进行同样的判断，最终取最大值进行返回。
时间复杂度O（n2），空间复杂度O（1）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        int count = 1;
        StringBuilder stringBuilder = new StringBuilder().append(s.charAt(0));
        char subString;
        for (int i = 1; i < s.length(); i++) {
            subString = s.charAt(i);
            for (int j = 0; j < stringBuilder.length(); j++) {
                if (stringBuilder.charAt(j) == subString) {
                    stringBuilder.delete(0, j + 1);
                    break;
                }
            }
            stringBuilder.append(subString);
            if (stringBuilder.length() > count) {
                count = stringBuilder.length();
            }
        }
        return count;
    }
}

解题二：

动态规划方案，使用Map给遍历过的值打上标记。
时间复杂度O（n），空间复杂度O（n）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<String, Integer> hashMap = new HashMap();
        String subString;
        Integer result = 0;
        Integer start = 0;
        Integer len = s.length();
        for (int i = 0; i < len; i++) {
            subString = String.valueOf(s.charAt(i));
            //妙啊，start初始化没值则为初始下标索引，如果记录的索引出现非null值，则判断当前的start和索引的start哪个更大，
            //则使用哪个，这样保证了可以使用到上一个值。
            //start就只会受到初始化值、记录索引值的影响，并保证用最大的值。
            start = Math.max(start, hashMap.getOrDefault(subString, -1) + 1);
            //最新的长度为：当前下标 - 上一次的值 + 1
            result = Math.max(result, i - start + 1);
            //缓存值
            hashMap.put(subString, i);
            // System.out.println(hashMap);
            // System.out.println(result);
        }
        return result;
    }
}