LeetCode-3-无重复字符的最长子字符串

思路一:（该解法面对最后的大字符串[31000个字符]会超时)

因为题目中要求取不存在重复字符的最大字符串，第一想法是想理解成贪心问题，总的长度为n，判断k个格子的不重复子字符串是否存在。如求取当1个字符长度的不重复字符串是否存在；2个字符长度的不重复字符串是否存在；3个字符长度的不重复字符串是否存在...n个字符长度的不重复字符串是否存在

代码如下：

// 再次提醒，该解法不能完全解出题目，最后一个大字符串用例因为超时无法通过，仅提供一种实现思路

class Solution {
    public int lengthOfLongestSubstring(String s) {

        // 思路借鉴动态规划划格子方法

        int len = s.length();
        if (len == 0) return 0;
        int max = 1;
	// 最小的格子 1 到最大的格子 len
        for (int i = 1 ; i <= len ; i++) {
	    // 判断该格子下的不重复子字符串是否存在
            for(int start = 0; start <= len - i; start ++ ) {
                char[] copy = new char[i];
                s.getChars(start, start + i,copy,0);
                if(unRepeat(copy)) {
                    max = i;
		    break;
                }
            }
        }
        return max;
    }
    // 重复返回false
    boolean unRepeat(char[] chars) {
        Set s = new HashSet();
        for (char ch: chars) {
            if(!s.contains(ch)) {
                s.add(ch);
            } else {
                return false;
            }
        }
        return true;
    }
}

思路二（正规题解）
使用滑动窗口解决问题

设置变量记录滑动过程中的子字符串最大值
该字符串最长子串是不定变化的，因此在遇到重复字符串的时候需要修改滑动窗口的大小，即把窗口的最左边界进行调整
调整的方法是将left边界值调整到Max(left,重复子字符串位置 + 1),因为窗口中如果包含该字符串则说明窗口中存在重复，需要收缩窗口的左边界
然后窗口不断的向右遍历到最后一个字符
为了快速查到是否为重复的字符串使用hashmap来记录，字符和字符位置，遇到相同字符的时候需要更新字符位置

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 1. 设置变量记录最大值
        // 2. 遇到重复字符串的时候调整窗口边界
        // 3. 遍历处理到字符串的最右边
        // 4. 使用map记录字符串和字符串位置
        
	// 字符串长度 
        int len = s.length();
        int left = 0; // 左窗口
        int right = 0; // 右窗口 
        int max = 0; // 最长子串
	// 记录字符和字符位置
        Map<Character,Integer> charMap = new HashMap<>();
        while (right < len) {
            if(charMap.containsKey(s.charAt(right))) {
		// 这里使用Math.max是因为可能会发生新发现的重复字符在map中存储的位置在窗口最左边界外
                left = Math.max(left,charMap.get(s.charAt(right)) + 1);
            }
	    // 更新字符位置
            charMap.put(s.charAt(right), right);
            max = Math.max(max, right - left + 1);
            // 滑动右窗口
            right++;
        }

        return max;
    }
}