Longest Substring without Repeating Characters (#3 Leetcode)

There is a difference between subsequence and substring.

A Substring takes out characters from a string placed between two specified indices in a continuous order. On the other hand, subsequence can be derived from another sequence by deleting some or none of the elements in between but always maintaining the relative order of elements in the original sequence. Click here for all subsequence problems

Problem Statement

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

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

The substrings are abc, bca, cab, abc, bcb, cb, b.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104

• s consists of English letters, digits, symbols and spaces.

Initially I tried to solve it using one for loop, but it didn't work for the input 'pwwkew' and 'dvdf' because when a character is repeated in substring S of ij, I will start from the next character.  But I supposed to start from the character which is next to repeating. Here is the code. 

#define RANGE 255
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //cout << "************" << s << endl;
        int longSubLen = 0, maxLen = 0;
        int count[RANGE] = {0};
        for (int i = 0; i < s.length(); i++) {
            ++count[s[i]];
              if (count[s[i]] > 1) {
                memset(count, 0, sizeof(count));
               //cout << " Inside if: s[" << i << "] " << s[i] << " count " << count[s[i] - 'a'] << endl;
                ++count[s[i]];
                maxLen = max(maxLen, longSubLen);
                longSubLen = 1;
                continue;
            } 
            longSubLen++;
            maxLen = max(maxLen, longSubLen);
            //cout << "s[" << i << "] " << s[i] << " longSubLen " <<  longSubLen << endl;
        }
        return maxLen;
    }
};

The above code didn't work for the string dvdf because the maxLen was 2(df). It should be 3(vdf). 

Later, I changed my code to have two for loops and an array to track of the visited elements in the array. 

#define RANGE 255
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //cout << "************" << s << endl;
        int longSubLen = 1, maxLen = 0;
        bool count[RANGE];
        for (int i = 0; s[i] != '\0' && i < s.length(); i++) {
            //cout << " *****s[" <<  i  << "] ****" << s[i] << endl;
            memset(count, false, sizeof(count));
            count[s[i]] = true;
            longSubLen = 1;
            maxLen = max(maxLen, longSubLen);
            for (int j = i+1; s[j] != '\0' && j < s.length(); j++) { 
                //cout << "s[" << j << "] " << s[j] <<  endl;
                if (s[i] == s[j] || count[s[j]] == true) {
                    break;
                }
                count[s[j]] = true;
                longSubLen++;
                maxLen = max(maxLen, longSubLen);
                //cout << "s[" << j << "] " << s[j] << " longSubLen " <<  longSubLen << endl;
            }
        }
        return maxLen;
    }
};

The following inputs should produce the outputs mentioned.

"abcabcbb" ==> 3

"bbbbb" ==> 1

"pwwkew" ==> 3

"dvdf" ==> 3

"ohvhjdml" ==> 6

"" ==> 0

" " ==> 1

         "yayjashvlfglgqukwmmhiodcesehmqrmqpvtjeoumufukaejorsyhwaloeuculolal"  

The time complexity of this problem is O(n^2), so this will not be an optimal approach. As I'm comparing every i-th element with j-th element. 

But, I got an idea like why can't we track which element is repeating with single loop. Here is the algorithm or solution. 

1. Traverse the character one by one and store the index. 

2. While traversing to the next character, check the index value of that particular next char. 

3. If the character repeats, it will definitely hold the index value already. 

4. Get this index. Move the window left from the next character of this index.

To learn more about sliding window, click here. 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int start = -1, res = 0;     
        vector<int> count(255, -1);
        
        for (int j = 0; j != s.length(); j++) {
           /* 
            * For example, abcabcbb is the input. When j is 3, count['a'] is 0.
            * As the substring shouldn't contain same characters, 
            * window will be moved to 1st index. So that Oth index will not be 
            * counted in the substring. 
            */
           if (count[s[j]] > start)  {
               /* 
                * To move the window from the left
                */
               start = count[s[j]];
           }
           res = max(res, j - start);
           count[s[j]] = j;
        }
        return res;   
    }
};

This is not count/frequency array(vector) but to store the position. As the position starts from 0 already, we need to initialise it with something else, that's the reason it is initiliased with -1

If start is 0, the condition "count[s[j]] > start" will not work for the next repeating character. 

The memory usage is 6.8 MB when I used count[] and 8.4 MB when I used vector. 

The running time is always 3 to 4 ms regardless of the vector or array. 

Complexity Analysis

• Time complexity : $O(n)$. Index $j$ will iterate $n$ times.

• Space complexity (HashMap) : $O(min(m, n))$. Same as the previous approach.

• Space complexity (Table): $O(m)$. $m$ is the size of the charset.

Other Sliding Window Problems:

Maximum Subarray Sum

Longest substring with replacement (#424 Leetcode)