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) {
            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

2 thoughts on “003. Longest Substring Without Repeating Characters

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s