1.直接哈希法. 复杂度
在扫描完所有的s[0...n]，s[1...n]，s[2...n]....后，最长的极长字符串就是字长不重复子串
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.empty())
return 0;
int visit[256];
int max_length=1;
int max_index=0;
for (int i = 0; i < s.size(); i++)
{
memset(visit, 0, sizeof(int)* 256);
int count = 1;
visit[s[i]] = 1;
max_index = i;
for (int j = i+1; j < s.size(); j++)
{
if (visit[s[j]] == 1)
break;
else
{
count++;
visit[s[j]] = 1;
if (count>max_length)
{
max_index = i;
max_length = count;
}
}
}
}
return max_length;
}
};
string stringToString(string input) {
assert(input.length() >= 2);
string result;
for (int i = 0; i < input.length(); i++) {
char currentChar = input[i];
if (input[i] == '\\') {
char nextChar = input[i + 1];
switch (nextChar) {
case '\"': result.push_back('\"'); break;
case '/': result.push_back('/'); break;
case '\\': result.push_back('\\'); break;
case 'b': result.push_back('\b'); break;
case 'f': result.push_back('\f'); break;
case 'r': result.push_back('\r'); break;
case 'n': result.push_back('\n'); break;
case 't': result.push_back('\t'); break;
default: break;
}
i++;
}
else {
result.push_back(currentChar);
}
}
return result;
}
int main() {
string line;
while (getline(cin, line)) {
string s = stringToString(line);
int ret = Solution().lengthOfLongestSubstring(s);
string out = to_string(ret);
cout << out << endl;
}
return 0;
}
2.滑动窗口
比方说 abcabccc 当你右边扫描到abca的时候你得把第一个a删掉得到bca，然后"窗口"继续向右滑动，每当加到一个新char的时候，左边检查有无重复的char，然后如果没有重复的就正常添加，有重复的话就左边扔掉一部分（从最左到重复char这段扔掉），在这个过程中记录最大窗口长度。
注意以下两点：
- 判断 std 中的 map 中是否有 key
- 存在重复的key,至于为什么取max,考虑出现多个重复的值情形
c++ code:
#include <iostream>
#include <string>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.empty())
return 0;
int max_length=0;
map<char, int>hashmap;
int left = 0;
for (int i = 0; i < s.length(); i++)
{
if (hashmap.find(s[i]) != hashmap.end())//判断 std 中的 map 中是否有 key
{
//left = hashmap[s[i]] + 1;//存在重复的key,至于为什么取max
left = max(left,hashmap[s[i]]+1);//存在重复的key,至于为什么取max,考虑出现多个重复的值情形
}
max_length = max(max_length, i - left + 1);
hashmap[s[i]] = i;
}
return max_length;
}
};
int main() {
string line="abcabc";
while (getline(cin, line))
{
Solution solu;
cout<<solu.lengthOfLongestSubstring(line) << endl;
}
return 0;
}
python code：
#!/usr/bin/env python
#-*- coding:UTF-8 -*-
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_len=0
d={}
left=0
for i in range(len(s)):
if s[i] in d:
left=max(left,d[s[i]]+1)
max_len=max(max_len,i-left+1)#注意这里是i不是d[s[i]]
d[s[i]]= i
return max_len
if __name__ == '__main__':
s="asxasx"
ret = Solution().lengthOfLongestSubstring(s)
print(ret)
