LeetCode 3 -- Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

在一个字符串中求不重复子串的最大长度是一个经典的贪心法求解问题（说子串自然是连续的，子序列则不要求连续）。

 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         if(s==null && s.length()==0)
 4         return 0;
 5     HashSet<Character> set = new HashSet<Character>();
 6     int max = 0;
 7     int walker = 0;
 8     int runner = 0;
 9     while(runner<s.length())
10     {
11         if(set.contains(s.charAt(runner)))
12         {
13             if(max<runner-walker)
14             {
15                 max = runner-walker;
16             }
17             while(s.charAt(walker)!=s.charAt(runner))
18             {
19                 set.remove(s.charAt(walker));
20                 walker++;
21             }
22             walker++;
23         }
24         else
25         {
26             set.add(s.charAt(runner));
27         }
28         runner++;
29     }
30     max = Math.max(max,runner-walker);
31     return max;
32     }
33 }

算法复杂度O（n），空间复杂度O（n）。

另外一种C++更简洁

 1 class Solution {
 2 public:
 3   int lengthOfLongestSubstring(string s) {
 4     unordered_map<char,int> um;//um记录遍历过程中每个字符最后出现的位置
 5     int res=0,i=0,j=0; //j记录当前不重复子串的起点，i记录当前不重复子串的终点
 6 
 7     while(i<s.size()){ //遍历字符串
 8       if(um.find(s[i])!=um.end() && um[s[i]]>=j ) //如果当前维护的不重复子串中出现了s[i]
 9         j=um[s[i]]+1;   //更新j
10       else  //如果当前维护的不重复子串中没有出现s[i]
11         res=max(res,i-j+1); //更新结果，取较大者
12 
13       um[s[i]]=i; //更新um
14       i++;
15     }
16     return res;
17   }
18 };

算法时间复杂度O(n)，空间复杂度O(1)。因为ASCLL码字符个数128个，这里用unorder_map打表记录每个字符在字符串中最后出现的位置，unordered_map的空间消耗最大为128，所以时间复杂度是常数级的。unordered_map的查找插入操作的时间复杂度都是O(1)，所以整个算法的时间度为O(n)。