Algorithm Puzzles: Longest Substring Without Repeating Characters

Posted on | In | Views:
Symbols count in article: 3.1k | Reading time ≈ 3 mins.

Algorithm Puzzles everyday every week sometimes: Longest Substring Without Repeating Characters

Puzzle

Puzzle from leetcode:

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solving

First came out solution

Traverse substring(not all of them, with a little bit optimization)

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
27
class Solution {
public:
    int lengthOfLongestSubstring(const std::string& s) {
        int longest = 0;
        for(int i = 0; i < s.size(); i++){
            for(int j = i + 1; j < s.size() + 1; j++){
                if((j-i) <= longest){
                    continue;
                }
                if(checkStringUnique(s.substr(i,j-i)))
                    longest = (longest > (j - i)) ? longest : (j - i);
                else
                    break;
            }
        }
        return longest;
    }
private:
    bool checkStringUnique(std::string&& s){
        for(auto iter = s.begin(); iter != s.end(); ++iter){
            if(s.find_first_of(*iter, std::distance(s.begin(), iter)+1) != std::string::npos){
                return false;
            }
        }
        return true;
    }
};

Time complexity: O(n^3)

But this solution is not good enough since the time complexity is O(n^3). Only better than 62.78% cpp users.

Sliding Window

Checked the reference answer, there is another solution: using sliding Window. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
     int lengthOfLongestSubstring(const std::string& s) {
        int n = s.size();
        int ans = 0;
        std::unordered_map<char, int> map;
        for (int j = 0, i = 0; j < n; j++) {
            auto res = map.find(s[j]);
            if (res != map.end()) {
                i = (res->second > i) ? res->second : i;
                res->second = j + 1;
            }else{
                map.insert({s[j], j + 1});
            }
            ans = (ans > (j - i + 1)) ? ans : (j - i + 1);
            
        }
        return ans;
    }
};

Time complexity: O(n)

It’s better than 85.71% now.

Assuming ASCII 128

The third way to solve this is assuming the string inputs are all ASCII 128 characters… In this case no hash table is needed.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
     int lengthOfLongestSubstring(const std::string& s) {
        int n = s.length(), ans = 0;
        int index[128] = {0};
        for (int j = 0, i = 0; j < n; j++) {
            i = index[s[j]] > i ? index[s[j]] : i;
            ans = (ans > (j - i + 1)) ? ans : (j - i + 1);
            index[s[j]] = j + 1;
        }
        return ans;
    }
};

This solution is faster than 95.65%.