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.

# 思路

理解一下题意，找出连续的，最长的，不重复的子串。注意，一定要是连续的，不是一个序列。如s = {p, w, w, k, e, w}，最长的不是{p, w, k, e}，因为{p, w, w, k}中间间隔了重复元素w，此时子串已从w断开。

暴力破解法：

大概流程是，我们计算每一位上的子串长度，取之中最长子串。

具体来说，从第i位起，我们把之后每一个位置上的字符加入集合，直到遇到重复字符。由于集合元素的单一性，此时元素为无法加入集合，此时的集合长度也是最长。比较当前集合的规模与之前最大的非重复子串规模，若大，更新后者为前者，若小，放弃。之后清空集合。继续i + 1位。

// brute force: time O(n ^ 3) space O(n) result: TLE public string LongestPalindrome(string s) { char[] strs = s.ToCharArray(); int start = 0, end = 0; for (int i = 0; i < strs.Length; i++) // start by index i { for (int j = strs.Length - 1; j > i; j--) // end by index j { if (strs[i] == strs[j]) { bool isPalindrome = true; for (int k = i + 1, l = j - 1; k < l; k++, l--) // check whether substring is palindrome or not { if (strs[k] != strs[l]) { isPalindrome = false; break; } } if (isPalindrome && j - i > end - start) // compare { start = i; end = j; } } } } return new string(strs, start, end - start + 1); }

暴力破解法，时间复杂度O(n ^ 3) （注意集合有搜索的时间），空间复杂度O(n)，时间TLE。

俗话说樯橹灰飞烟灭，的确是这样。

暴力破解法是一种欠缺思考的方法，他充分利用了计算机的计算性。可是当数据规模过于庞大时，计算机的计算能力还是吃不消的（或许量子计算机可以），所以我们要对计算过程优化，要勤于思考，寻找计算过程的一些性质，加速计算过程。

现在有这样一串，s = {a, b, c, d, a, f, e}。

暴力破解的话，首先对于第0位的字符a，我们会将a, b, c, d加入集合，之后遇到重复的a，此时比较最长不重复子串，更新长度为4。

之后，暴力破解的做法为，从第1位的字符b起，重新计算最长不重复子串长度。

事实上，我们没有必要从第1位字符b起计算最长不重复子串。我们只需要剔除之前的a，加入重复的a。由于在a之前并没有重复，a是第一个重复的字符，故这个子串肯定是从b开始最短的不重复子串。我们只需要从重复的a之后一位起，继续计算不重复子串的长度。

带有技巧的暴力破解：

我们用链表来实现元素的保存。一直将元素加入链表，直到遇到重复元素。此时将重复元素第一次出现位置（包括该位置）之前的元素全部删除，再将重复元素加入。继续上述过程。

举个例子，s = {p, w, w, k, e, w}。

链表 = {p} => {p, w} => {w} （w重复了，删除第一个w和之前的元素，并加入重复元素w） => {w, k} => {w, k, e} => {k, e, w} （w重复了，删除第一个w和w之前元素（实际没有），并加入重复元素w）。

最长不重复子串长度 = 0 => 0 => 2 （子串重复的时候我们再计算没重复子串的长度，节约时间） => 2 => 2 => 3 （=> 3（检查最后一个不重复子串是否最长））

// if c exists in the LinkedList, returns the location of c, else returns the size of LinkedList public int find(LinkedList<char> list, char c) { LinkedListNode<char> node = list.First; int loc = 0; while (node != null) { if (node.Value == c) { break; } else { node = node.Next; loc++; } } return loc; } // remove c and before c‘s element in the LinkedList public void remove(LinkedList<char> list, char c) { LinkedListNode<char> node = list.First; while (node != null && node.Value != c) { node = node.Next; list.RemoveFirst(); } list.RemoveFirst(); } // We add the string‘s element into a sequence set, until at a certain moment, when we find a repeat. // At this time, we calculate the max length of substring, // and remove elements before the repeat element first appeared in the string(include the repeat element), // and add repeat element into the end of set. If we get to the end of string, we will calculate maxLength again // (possibly there is no repeat in string or the last substring is longest, so it is necessary to calculate at last). // e.g. string = "pwwkew" // set = {p} => {p, w} => (w repeat and remove elements including w and in front of first w (which is p) and add w athe the end of set) {w} // => {w, k} => {w, k ,e} => {k, e, w} // maxLength = 0 => (we don‘t find a repeat so we don‘t calculate for saving time) 0 => (find repeat and calculate maxLength) 2 // => 2 => 2 => 3 (=> 3 (last substring)) // tricky brute force: time O(n ^ 2) Spcae O(n) result: 160ms public int LengthOfLongestSubstring(string s) { if (s.Length == 0) return 0; // don‘t forget char[] strings = s.ToCharArray(); int maxCount = 0; LinkedList<char> list = new LinkedList<char>(); list.AddFirst(strings[0]); for (int i = 1; i < s.Length; i++) { if (find(list, strings[i]) == list.Count) { list.AddAfter(list.Last, strings[i]); } else { if (list.Count > maxCount) maxCount = list.Count; remove(list, strings[i]); list.AddLast(strings[i]); } } // check again if (list.Count > maxCount) return list.Count; else return maxCount; }