[LeetCode]3. Longest Substring Without Repeating Characters

原题链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

意思是给定字符串，输出无重复字符的最长子串长度

我的实现（Brute Force）生成全部无重复子串，从而得到最大长度：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_length = 0;
        
        if (!s.empty())
            max_length = 1;
        
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                string sub = s.substr(i, j - i);
                int pos = sub.find(s.at(j));
                if (pos == string::npos) {
                    if (max_length < sub.length() + 1)
                        max_length = sub.length() + 1;
                } else {
                    break;
                }
            }
        }
        
        return max_length;
    }
};

时间复杂度：O(n​³​​).

空间复杂度：O(n). 

如何提升：

Sliding Window + HashSet

Sliding Window：指的是由起始和终止索引所确定的子段[i,j) (left-closed, right-open). 

HashSet：集合元素的唯一性，比起我用字符串好多了（无重复元素的问题）

思想：[i, j-1]已知无重复字符，只需判断是否要拓展j：

1.如果j位置的字符在集合中已存在，则对于i开始的最长无重复字符串在j-1时就结束了，接下来开始寻找i+1开始的最长无重复字符串，同时字符集合中需去除i位置字符；

2.如果j位置的字符在集合中不存在，则将j位置的字符加入字符集合，再判断是否拓展j+1。

可以看到它的重点在于字符集合和已经确定了无重复字符段的使用。实现代码（Java）：

public class Solution {
    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;
    }
}

时间复杂度：O(n).

空间复杂度：O(min(m,n)). m为字符集合的长度

在Sliding Window基础上进一步优化：

前面我们是发现重复字符就将i加1，但可能i位置的字符并不是重复的字符，我们可以直接跳到Sliding Window中重复字符所在位置的后面，不用每次将i加1，从而避免了一些无意义的操作；获取Sliding Window中重复字符位置可以用HashMap或者一个数组。实现如下：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

总结：Set、已确定无重复段的使用，对重复字符位置的处理。