【Leetcode】【Medium】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，o(n)：

新建一个字符串变量sub用来保存当前处理的子字符串，从起始遍历原字符串S中的每个字符；

对于每一个遍历到的字符S[i]：

　　如果S[i]已存在sub中（例sub[j] = S[i]），则sub切掉sub[j]及其之前的所有字符，并在末尾插入S[i];

　　如果S[i]不存在sub中，则在sub末尾插入S[i]。

　　遍历过程中，随时记录sub曾经达到的最大长度maxlength

遍历结束，返回maxlength；

代码：

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int string_length = s.size();
 5         if (string_length <= 1) 
 6             return string_length;
 7             
 8         string substring = string(1, s[0]);
 9         int current_length = 1;
10         int max_length = 1;
11         
12         for (int i = 1; i < string_length; ++i) { //current_length + string_length - i > longest_length
13             int pos = substring.find(s[i]);
14             if (pos != -1) {
15                 substring = substring.substr(pos + 1) + s[i];
16                 current_length -= pos;
17             } else {
18                 substring += s[i];
19                 current_length++;
20                 if (current_length > max_length)
21                     max_length = current_length;
22             }
23         }
24         
25         return max_length;
26     }
27 };

解题思路2，o(n)：

用一个128个元素的int型数组postions，记录字符串中的每个字符，在字符串中上次出现的位置（之前从未出现则为-1）；同时用一个int变量ind记录子串的开始位置；

当遍历到字符串某一个元素S[i]时：

　　查看postion数组中记录的此字符上次出现的位置positions[S[i]]，

　　如果positions[S[i]]大于ind，说明S[i]在当前子串中有重复，则ind = positions[S[i]] + 1；

　　如果positions[S[i]]小于ind，说明当前子串中，不包含S[i]，则ind不变；

　　随时记录子串的最大长度（i - ind + 1）

循环结束，返回最大长度值。

代码：

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int positions[128];
 5         memset(positions, -1, sizeof(positions));
 6 
 7         int ind = 0;
 8         int max = 0;
 9         for (int i = 0; i < s.size(); i++){
10             if (positions[s[i]] >= ind)
11                 ind = positions[s[i]] + 1;
12 
13             if (i - ind + 1 > max)
14                 max = i - ind + 1;
15 
16             positions[s[i]] = i;
17         }
18         
19         return max;
20     }
21 };

附录：

C++ string操作