https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Description
要求在一个字符串中寻找最长的没有重复字符的子串。注意，是子串(substring)，不是子序列(subsequence)。
思路1：Brute Force
暴力的做法简而言之就是：遍历字符串所有的位置，以这个位置为起点往前走，找出满足要求的子串。
具体地，可以用两个指针维护子串的区间，每往前走一格，须要判断当前位置的字符在区间内是否重复出现（暴力的做法是扫描这个区间，较好的做法是用一个Hash Set存储区间内的元素，从而可以O(1)查找）。
Time complexity: 最最暴力的算法是O(n^3)，用Hash Set的话就是O(n^2)
Space complexity: 用Hash Set的话就是O(字符种类数)，否则O(1)
ps. O(n^2)的算法可以AC
参考代码(C++)
class Solution { public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) return 0;if (n == 1) return 1;int ret = 1;int start = 0, end = 1;while (end < n) {int tmp_ret = 1;unordered_set<int> myset({s[start]});while (end < n && myset.find(s[end]) == myset.end()) {myset.insert(s[end]);tmp_ret++;end++;}ret = max(ret, tmp_ret);start++; end = start + 1;}return ret;} };思路2：Sliding Window / Two Pointers
将longest substring without repeating characters简称为"LSWRC"。
扫描一遍字符串，对每个位置，计算以该位置的字符为终点的LSWRC的长度，取最大的。
具体地，设字符串为s，用s[i]表示位置i的字符，设以s[i]为终点的LSWRC的长度对应的区间是[start, i]。然后据此计算位置i+1的LSWRC，分两种情况：
- 如果
s[i+1]在s[start...i]未出现，则新的区间为[start, i+1]； - 如果
s[i+1]在s[start...i]出现了，设出现的位置是p (start <= p <= i)，则须要更新区间为[p+1, i+1]。
实现上，可以用两个变量维护区间的边界信息，用一个哈希表存储区间的元素以快速查找。这里有一个小技巧，不需要真的去存区间的元素，否则还要删除（虽然删除的开销并不大），直接存目前为止的所有元素，查找的时候如果找到了重复元素，再判断找到的元素是否在[start, i]区间内即可，不在的话就按情况1更新区间。
Time complexity: O(n)
Space complexity: O(字符种类数)
参考代码(C++)
class Solution { public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) return 0;if (n == 1) return 1;int ret = 1, cur_ret = 1;unordered_map<char, int> hash_map; // key: element of s, value: index of the elementhash_map[s[0]] = 0;int start = 0;for (int i = 1; i < n; ++i) {unordered_map<char, int>::iterator it = hash_map.find(s[i]);if (it == hash_map.end()) {hash_map[s[i]] = i;} else {if (it->second >= start) {start = it->second + 1;}it->second = i; // update the pos of repeated char}ret = max(ret, i-start+1);}return ret;} };