codekofi
← All questions

Longest Substring Without Repeating Characters

HardSliding Window

The problem

Given a string, return the length of the longest substring that contains no repeated character.

A substring is contiguous.

lengthOfLongestSubstring("abcabcbb")

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int lengthOfLongestSubstring(const string& s) {
2
3 int n = s.size();
4 unordered_map<char, int> lastSeen;
5
6 int start = 0;
7 int ans = 1;
8
9 for (int i = 0; i <= n; i++) {
10
11 char c = s[i];
12
13 if (lastSeen.count(c) && lastSeen[c] >= start) {
14 start = lastSeen[c] + 1;
15 }
16
17 lastSeen[c] = i;
18
19 int width = i - start + 1;
20
21 if (width > ans) {
22 ans = width;
23 }
24 }
25
26 return ans;
27}
1int lengthOfLongestSubstring(const string& s) {
2
3 int n = s.size();
4 unordered_map<char, int> lastSeen;
5
6 int start = 0;
7 int ans = 0;
8
9 for (int i = 0; i < n; i++) {
10
11 char c = s[i];
12
13 if (lastSeen.count(c) && lastSeen[c] >= start) {
14 start = lastSeen[c] + 1;
15 }
16
17 lastSeen[c] = i;
18
19 int width = i - start + 1;
20
21 if (width > ans) {
22 ans = width;
23 }
24 }
25
26 return ans;
27}
1int lengthOfLongestSubstring(const string& s) {
2
3 int n = s.size();
4 unordered_map<char, int> lastSeen;
5
6 int start = 0;
7 int ans = 1;
8
9 for (int i = 0; i < n; i++) {
10
11 char c = s[i];
12
13 if (lastSeen.count(c) && lastSeen[c] >= start) {
14 start = lastSeen[c - 1] + 1;
15 }
16
17 lastSeen[c] = i;
18
19 int width = i - start + 1;
20
21 if (width > ans) {
22 ans = width;
23 }
24 }
25
26 return ans;
27}