# 003. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Questions:

1. upper case and lower case characters are same or not?

2. whether there is only 1 solution.

Test cases:

1. empty string
2. a
3. bbbbbb
4. abcabcbcbb: dup is in the window
5. tmmzuxt: dup is not in the window

Solution 1:

Data structure:
string, unordered_map
Method:
two pointers, hash table
Steps:
1. loop through the string using head and tail, for each char
2.1 fix head, move tail
2.1 if it is not in the hash map, insert(char, index)
2.2 if it is in the hash map, and index >= head, move head to old_index + 1, and replace with new index,
2.2 max_length = max(max_length, tail – head + 1)
Complexity:
runtime: O(N)
space: O(N)
Code:
```class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (!n) return 0;
unordered_map<char, int> m;
int head = 0, tail = 0, result = 0;
while (tail < n) {
if (m.find(s[tail]) != m.end() && m[s[tail]] >= head) {
head = m[s[tail]] + 1;
}
m[s[tail]] = tail;
result = max(result, tail - head + 1);
tail++;
}
return result;
}
};
```

Solution 2:
Data structure:
string, array
Method:
two pointers
Steps:
same with Method 1, but using array instead of unordered_map.
Complexity:
runtime: O(N)
space: O(N)
Code:
```class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (!n) return 0;
vector<int> m(256, -1);
int head = 0, tail = 0, result = 0;
while (tail < n) {
m[s[tail]] = tail;
result = max(result, tail - head + 1);
tail++;
}
return result;
}
};
```

Submission errors:

1. wrong answer. Did not consider the case that dup is not in the window.

Things to learn:
1. good test case can help find bug.
2. when input range is known, we can use array instead of hash map to improve the performance.
3. the ASCII table has 128 characters, with values from 0 through 127. Thus, 7 bits are sufficient to represent a character in ASCII; however, most computers typically reserve 1 byte, (8 bits), for an ASCII character.