问题

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 subsequenceand not a substring.

分析

首先，这种题肯定不能暴力来解决，否则肯定会超时。所以，考虑用一个哈希表（Map<char, int>）来维护状态。key是字符，value是当前字符出现在字符串的位置。

可能有个疑问，为什么这道题归类到“动态规划”中。动态规划类题目中的一共特性就是要有一个状态转移方程，可是这道题直接看起来并没有。但其实，思想是相同通。即当前状态的解要根据之前上一状态的信息来求解。只不过求解的过程不能用一个状态转移方程来解决，所以我认为这道题也有着动态规划的思想。

时间复杂度

O(n)

代码

[code lang=”cpp”]
/**
* https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description
*
* dp
*/
#include <iostream>
#include <vector>
#include
<map>
#include <string>

using namespace std;

#define MAX 1000000001

class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> dp;
int max_length = -1, cur_length = 0, cur_offset = 0, length = s.size(), last_offset = 0;
for (int i = 1; i < length + 1; ++i) {
map<char, int>::iterator it = dp.find(s[i – 1]);
if (it != dp.end() && it->second >= cur_offset) {
last_offset = it->second;
cur_offset = last_offset + 1;
cur_length = i – cur_offset + 1;
} else {
if (++cur_length > max_length) max_length = cur_length;
dp.insert(pair<char, int>(s[i – 1], i));
}
it->second = i;// re-write the current pos for the cur char
}
return max_length > 0 ? max_length : 0;
}
};

int main(int argc, char * argv[]) {
Solution * s = new Solution();
cout<<s->lengthOfLongestSubstring("qwnfenpglqdq");
}
[/code]

问题来源：https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description