Title Description

Given a string, please find out the length of the longest substring that does not contain duplicate characters.

Type: "abcabcbb"
Output: 3 
Explanation: because the longest substring without repeating characters is "abc", its length is 3.

Enter: "bbbbb"
Output: 1
 Explanation: because the longest substring without repeating characters is "b", its length is 1.

Enter: "pwwkew"
Output: 3
 Explanation: because the longest substring without repeating characters is "wke", its length is 3.
     Note that your answer must be the length of the substring, "pwke" is a substring, not a substring.

Algorithm analysis

• Through i,j to build a sliding window. (because only consecutive substrings) to O(n).
• Each step needs to find and add a corresponding point, whether it already exists in the original table. On the cpp, I use a queue in and out of the queue to simulate. At the same time, a hash table is built to locate with O(1) complexity.

Ideas for improvement: queues don't seem to be useful in this step. Use the cursor i directly to record the value of the left window.

Original code

#include <queue>
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, i = 0, j = 0, max_=0, n=s.size();
        
        for(i = 0; i < s.size(); ++i) {
            max_ = (max_ > s[i]) ? max_ : s[i];
        }
        
        bool * b_ptr = new bool[max_+1];
        for(i = 0; i <= max_; ++i) {b_ptr[i] = false;}
        i = 0, j = 0;
        int tmp;
        queue<int> q;
        while (i < n && j < n) {
            if(!b_ptr[s[j]]) {
                b_ptr[s[j]]=true;
                q.push(s[j]);
                j++;
                ans = (ans > j - i) ? ans : j - i;
            } else {
                tmp = q.front();
                q.pop();
                i++;
                b_ptr[tmp]=false;
            }
        }
        delete[] b_ptr;
        return ans;
    }
};

Improved code

• Remove the queue and use i to locate the previous sequence

Further improvement: the array size is too large. The initialization time is also called the maximum lower limit.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, i = 0, j = 0, max_=0, n=s.size();
        
        for(i = 0; i < s.size(); ++i) {
            max_ = (max_ > s[i]) ? max_ : s[i];
        }
        
        bool * b_ptr = new bool[max_+1];
        for(i = 0; i <= max_; ++i) {b_ptr[i] = false;}
        i = 0, j = 0;
        int tmp;
        while (i < n && j < n) {
            if(!b_ptr[s[j]]) {
                b_ptr[s[j]]=true;
                j++;
                ans = (ans > j - i) ? ans : j - i;
            } else {
                tmp = s[i++];
                b_ptr[tmp]=false;
            }
        }
        delete[] b_ptr;
        return ans;
    }
};

Further improvement

• Make arrays smaller
• But the addition of every time to carry out an addition operation, which greatly affects the time efficiency.

According to the estimation, the length of ascii code is actually limited, so the space size will not change much, but the increase in time is unforgivable.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        int ans = 0, i = 0, j = 0, max_=0, n=s.size(), min_;
        
        for(i = 0; i < s.size(); ++i) {
            max_ = (max_ > s[i]) ? max_ : s[i];
            min_ = (min_ < s[i]) ? min_ : s[i];
        }
        
        bool * b_ptr = new bool[max_ - min_ + 1];
        for(i = 0; i <= max_ - min_; ++i) {b_ptr[i] = false;}
        i = 0, j = 0;
        int tmp;
        while (i < n && j < n) {
            if(!b_ptr[s[j] - min_]) {
                b_ptr[s[j] - min_]=true;
                j++;
                ans = (ans > j - i) ? ans : j - i;
            } else {
                tmp = s[i++];
                b_ptr[tmp - min_]=false;
            }
        }
        delete[] b_ptr;
        return ans;
    }
};