Longest Substring Without Repeating Characters

Question:

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.


Think Out Loud:

We want to find the longest substring without repeating characters. The first thing comes to my mind is that we need a hash table to store every character in a substring so that when a new character comes in, we can easily know whether this character is already in the substring or not. I call it as valueIdxHash. Then, a substring has a startIdx and endIdx. So we need a variable to keep track of the starting index of a substring and I call it as startIdx. Let's assume we are at index i and we already have a substring (startIdx, i - 1). Now, we want to check whether this substring can keep growing or not.

If the valueIdxHash contains str[i], it means it is a repeated character. But we still need to check whether this repeated character is in the substring (startIdx, i - 1). So we need to retrieve the index of str[i] that is appeared last time and then compare this index with startIdx.

  • If startIdx is larger, it means the last appeared str[i] is outside of the substring. Thus the subtring can keep growing.
  • If startIdx is smaller, it means the last appeared str[i] is within of the substring. Thus, the substring cannot grow any more. startIdx will be updated as valueIdxHash[str[i]] + 1 and the new substring (valueIdxHash[str[i]] + 1, i) has potential to keep growing.

If the valueIdxHash does not contain str[i], the substring can keep growing.

Show Me Your Code:

javascript
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const valueIdxHash = {};
    var longest = 0;
    var startIdx = 0;
    for(var i = 0; i < s.length; i++) {
        if(s[i] in valueIdxHash) { //constain s[i]
            var lastAppearanceIdx = valueIdxHash[s[i]];

            if (lastAppearanceIdx < startIdx) {
                //does nothing
            } else {
                startIdx = lastAppearanceIdx + 1;
            }

            valueIdxHash[s[i]] = i;
        } else { //does not contain s[i]
            valueIdxHash[s[i]] = i;            
        }

        longest = Math.max(longest, i - startIdx + 1);
    }
    return longest;
};

//simplified version
var lengthOfLongestSubstring = function(s) {
    const valueIdxHash = {};
    var longest = 0;
    var startIdx = 0;
    for(var i = 0; i < s.length; i++) {
        if(s[i] in valueIdxHash) {
            startIdx = Math.max(startIdx, valueIdxHash[s[i]] + 1);
        }
        valueIdxHash[s[i]] = i;
        longest = Math.max(longest, i - startIdx + 1);
    }
    return longest;
};
cpp
 int lengthOfLongestSubstring(string s) {
     if(s.size() <= 1)
         return s.size();

     unordered_map<int, int> value_idx_hash;//key is element, val is its index;
     int startIdx = 0;
     int longest = 0;

     for(int i = 0; i < s.size(); i++){
        if(value_idx_hash.find(s[i]) != value_idx_hash.end()){
            startIdx = max(startIdx, value_idx_hash[s[i]]+1);
        }
        value_idx_hash[s[i]] = i;

        longest = max(longest, i - startIdx + 1);
     }
     return longest;
 }

results matching ""

    No results matching ""