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) { head = max(head, m[s[tail]] + 1); 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**.
Advertisements

[…] Longest Substring Without Repeating Characters […]

LikeLike

[…] Longest Substring Without Repeating Characters […]

LikeLike