TIANYU'S HOMEPAGE
  • Home
  • Publications
  • Hobbies
  • BLOG
    • Planning & Control
    • Machine Learning
    • Game Theory
    • Python
    • Misc
  • Contact

Crack LeetCode

Technical interview questions can be pretty hard, at least when you are not prepared.
Let's get started!

3. Longest Substring Without Repeating Characters

12/29/2015

0 Comments

 

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

 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
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) 

 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
28
29
30
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
Copyright © [Tianyu Gu] [2016]. All rights reserved.
0 Comments



Leave a Reply.

  • Home
  • Publications
  • Hobbies
  • BLOG
    • Planning & Control
    • Machine Learning
    • Game Theory
    • Python
    • Misc
  • Contact