003. Longest Substring Without Repeating Characters

  • 23.9%

https://leetcode.com/problems/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.


leetcode 3

leetcode 76

leetcode 159

相似,模板相似,学习一下

方法一:

使用哈希表维护值和值的index

方法二:

既然是对数字的哈希,不如使用数组来的方便。

我的代码实现一:

实现效果最好。

最开始index都指向-1,指向开始索引的前一个位置,就是-1。

然后start就是指向索引的前一个位置。

一个end从0开始遍历至最后,start指向前一个位置。

更新时,先更新start,然后是length,最后更新索引,end++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n<=1)
return n;
vector<int> indexs(256, -1);
int start = -1, end = 0, length=0;
while(end < n){
start = max(start, indexs[s[end]]);
length = max(length, end-start);
indexs[s[end]] = end;
end++;
}
return length;
}
};

我的代码实现二:

实现逻辑清晰,但是不如上面代码。

字符要用256位,不要用26位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
int start = 0;
vector<int> v(256, -1);
for(int i=0; i<s.size(); i++){
if(v[s[i]]!=-1){
start = max(start, v[s[i]]+1);
res = max(res, i-start+1);
v[s[i]] = i;
}else{
res = max(res, i-start+1);
v[s[i]] = i;
}
}
return res;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> indexs(256, -1);
int length = 0, start = -1, end = 0;
int n = s.size();
while(end<n){
start = max(start, indexs[s[end]]);
length = max(length, end-start);
indexs[s[end]] = end;
end++;
}
return length;
}
};

code 1:

https://discuss.leetcode.com/topic/4083/shortest-o-n-dp-solution-with-explanations

Shortest O(n) DP solution with explanations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Solution (DP, O(n)):
*
* Assume L[i] = s[m...i], denotes the longest substring without repeating
* characters that ends up at s[i], and we keep a hashmap for every
* characters between m ... i, while storing <character, index> in the
* hashmap.
* We know that each character will appear only once.
* Then to find s[i+1]:
* 1) if s[i+1] does not appear in hashmap
* we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]
* 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k
* let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
* entry in hashmap to mark the latest occurency of s[i+1].
*
* Since we scan the string for only once, and the 'm' will also move from
* beginning to end for at most once. Overall complexity is O(n).
*
* If characters are all in ASCII, we could use array to mimic hashmap.
*/

int lengthOfLongestSubstring(string s) {
// for ASCII char sequence, use this as a hashmap
vector<int> charIndex(256, -1);
int longest = 0, m = 0;

for (int i = 0; i < s.length(); i++) {
m = max(charIndex[s[i]] + 1, m); // automatically takes care of -1 case
charIndex[s[i]] = i;
longest = max(longest, i - m + 1);
}

return longest;
}

code 2:

start 表示最长字符串起始的位置。

i表示终止的位置,或者说当前到达的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
};

方法三:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start = 0, length = 0, end = 0, cnt = 0;
vector<int> v(256, 0);
int n = s.size();
while(end<n){
if(v[s[end]]==1)
cnt++;
v[s[end]]++;
end++;
while(cnt>0){
if(v[s[start]]==2)
cnt--;
v[s[start]]--;
start++;
}
length = max(length, end-start);
}
return length;
}
};

有模板的,下面是详情

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
vector<int> map(128,0);
int counter=0, begin=0, end=0, d=0;
while(end<s.size()){
if(map[s[end++]]++>0) counter++;
while(counter>0) if(map[s[begin++]]-->1) counter--;
d=max(d, end-begin); //while valid, update d
}
return d;
}

我的代码实现一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n<=1) return n;
vector<int> indexs(256, 0);
int left = 0, right = 0, counter = 0, length = 0;
while(right<n){
if(indexs[s[right]]>0)
counter++;
indexs[s[right]]++;
right++;
while(counter>0){
if(indexs[s[left]]>1)
counter--;
indexs[s[left]]--;
left++;
}
length = max(length, right-left);
}
return length;
}
};

我的代码实现二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
int head = 0, end = 0, d = 0, cnt = 0;
vector<int> v(256, 0);
while(end < s.size()){
if(v[s[end]]!=0)
cnt++;
v[s[end]]++;
end++;
while(cnt>0){
if(v[s[head]]>1)
cnt--;
v[s[head]]--;
head++;
}

d = max(d, end - head);
}
return d;
}
};

学习区:

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

I will first give the solution then show you the magic template.

The code of solving this problem is below. It might be the shortest among all solutions provided in Discuss.

  1. Minimum Window Substring
1
2
3
4
5
6
7
8
9
10
11
12
13
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //in t
while(counter==0){ //valid
if(end-begin<d) d=end-(head=begin);
if(map[s[begin++]]++==0) counter++; //make it invalid
}
}
return d==INT_MAX? "":s.substr(head, d);
}

Here comes the template.

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one head
int d; //the length of substring

for() { /* initialize the hash map here */ }

while(end<s.size()){

if(map[s[end++]]-- ?){ /* modify counter here */ }

while(/* counter condition */){

/* update d here if finding minimum*/

//increase begin to make it invalid/valid again

if(map[s[begin++]]++ ?){ /*modify counter here*/ }
}

/* update d here if finding maximum*/
}
return d;
}

One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

The code of solving Longest Substring with At Most Two Distinct Characters is below:

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstringTwoDistinct(string s) {
vector<int> map(128, 0);
int counter=0, begin=0, end=0, d=0;
while(end<s.size()){
if(map[s[end++]]++==0) counter++;
while(counter>2) if(map[s[begin++]]--==1) counter--;
d=max(d, end-begin);
}
return d;
}

The code of solving Longest Substring Without Repeating Characters is below:

Update 01.04.2016, thanks @weiyi3 for advise.

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
vector<int> map(128,0);
int counter=0, begin=0, end=0, d=0;
while(end<s.size()){
if(map[s[end++]]++>0) counter++;
while(counter>0) if(map[s[begin++]]-->1) counter--;
d=max(d, end-begin); //while valid, update d
}
return d;
}

I think this post deserves some upvotes! : )



https://discuss.leetcode.com/topic/24739/c-code-in-9-lines

16ms, 62.39%, 23 July 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
};

https://discuss.leetcode.com/topic/1914/my-o-n-solution

My O(n) Solution

if only use DP, it’s an O(n*n) solution, adding a map to get O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()<2) return s.size();
int d=1, maxLen=1;
unordered_map<char,int> map;
map[s[0]]=0;
for(int i=1;i<s.size();i++)
{
if(map.count(s[i])==0 || map[s[i]]<i-d)
d++;
else
d= i- map[s[i]];
map[s[i]]=i;
if(d>maxLen)
maxLen = d;
}
return maxLen;
}
};

python


https://discuss.leetcode.com/topic/11632/a-python-solution-85ms-o-n

104ms, 84.17%, 23 July 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = maxLength = 0
usedChar = {}

for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i

return maxLength

java


https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation

11-line simple Java solution, O(n) with explanation

the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}

https://discuss.leetcode.com/topic/25499/share-my-java-solution-using-hashset

Share my Java solution using HashSet

The idea is use a hash set to track the longest substring without repeating characters so far, use a fast pointer j to see if character j is in the hash set or not, if not, great, add it to the hash set, move j forward and update the max length, otherwise, delete from the head by using a slow pointer i until we can put character j to the hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, max = 0;
Set<Character> set = new HashSet<>();

while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
max = Math.max(max, set.size());
} else {
set.remove(s.charAt(i++));
}
}

return max;
}

https://leetcode.com/articles/longest-substring-without-repeating-characters/

思路:双指针,j在前,i在后,如果s[j]不包含,则添加进哈希表,如果包含,则去掉i,i向后走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}

思路:建立map,不仅存字符还存字符的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}

与上一段代码思路相同

一个是length为0,return 0,检查特殊情况。

一个是做一个hashmap,存入获取的操作要好好看看。

22ms, 31.97%, 23 July 2016

https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation/1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
for(int i=0, j=0; i < s.length(); ++i){
if(map.containsKey(s.charAt(i)))
j = Math.max(j, map.get(s.charAt(i))+1);
map.put(s.charAt(i), i);
max = Math.max(max, i-j+1);
}
return max;
}
}

The previous implements all have no assumption on the charset of the string s.

If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

Commonly used tables are:

1
2
3
int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
谢谢你,可爱的朋友。