Description
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Solution
C++
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
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max = 0, head = -1, tail = 0;
int char_idx[256];
memset(char_idx, 0xff, sizeof(char_idx));
while(tail < s.size()) {
if (char_idx[s.at(tail)] > head) {
int length = tail - head;
if (length > max) {
max = length;
}
head = char_idx[s.at(tail)];
}
char_idx[s.at(tail)] = tail;
tail++;
}
int length = tail - head;
if (length > max) {
max = length;
}
return max - 1;
}
};
Runtime: 8 ms, faster than 89.14% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 6.7 MB, less than 99.87% of C++ online submissions for Longest Substring Without Repeating Characters.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lengthOfLongestSubstring(char * s){
int max = 0; // max length of longest substring
int pos[256];
memset(pos, 0xff, 256 * sizeof(int));
// sliding window
int rear = 0, front = 0;
int strlength = strlen(s);
for (; rear < strlength; rear++) {
int ascii_code = (int)s[rear];
if (pos[ascii_code] >= front) { // character repeats
int length = rear - front;
max = (max > length) ? max : length;
front = pos[ascii_code] + 1;
}
pos[ascii_code] = rear;
}
int length = rear - front;
max = (max > length) ? max : length;
return max;
}
Runtime: 0 ms, faster than 100.00% of C online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 5.8 MB, less than 93.33% of C online submissions for Longest Substring Without Repeating Characters.
