3. Longest Substring Without Repeating Characters

12/29/2015

Sol 1 (C++): hash table (set) + two pointers

int lengthOfLongestSubstring(string s) {
    if(s.length() == 0) return 0;

    int idx0 = 0;
    int idxf = 1;

    int maxLength = 1;

    unordered_set<char> set;
    set.insert(s[idx0]);

    while(idxf<s.length()) {
        if( set.find(s[idxf]) != set.end() ) {
            idxf--;
            set.erase(s[idx0]);
            idx0++;
        }
        else {
            set.insert(s[idxf]);
            maxLength = max(maxLength, idxf-idx0+1);
        }
       
        idxf++;
    }

    return maxLength;
}

Sol 2 (Python): hash table (map)

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    strLength = len(s)
    tmp = []
    charMap = dict(tmp)

    idx0 = 0
    idxf = 0

    maxLength = 0

    while idxf < strLength:
        charCurr = s[idxf]
        if charCurr in charMap:
            # remove the characters from idx0 to idxStop
            idxStop = charMap[charCurr]
            for id in range(idx0, idxStop+1):
                if s[id] in charMap:
                    del charMap[s[id]]
            charMap[charCurr] = idxf
            idx0 = idxStop + 1
        else:
            charMap[charCurr] = idxf
            maxLength = max( maxLength, idxf-idx0+1 )
        idxf+=1

    return maxLength

0 Comments

Crack LeetCode

3. Longest Substring Without Repeating Characters

Sol 1 (C++): hash table (set) + two pointers

Sol 2 (Python): hash table (map)

Leave a Reply.

Crack LeetCode

3. Longest Substring Without Repeating Characters﻿

Sol 1 (C++): hash table (set) + two pointers

Sol 2 (Python): hash table (map)