LeetCode: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

---

The idea is traversing the string, when we meet one letter already viewed, start from the next one of the previously recorded letter. For example, string is "abcadef", when we meet the second a, start counting from b and continue recording.

C++ Code:

/* func: length_of_longest_substring
 * goal: find the length of the longest substring which doesn't
    contain repeating characters
 * @param s: the input string
 * return: the length of the longest substring
 * complexity: near O(n)
 */
/*
 *basic idea: Check every possible substring when traversing the string
 */
int length_of_longest_substring(string s){
    //Use hash map to record the position of every letter
    unordered_map<char, int> charset;
    
    int result = 0;
    
    //iteration index
    int i = 0;
        
    while(i < s.size()){
        auto iter = charset.find(s.at(i));
        if(iter == charset.end()){
            //there is no duplication in current substring
            //insert the current one
            charset.emplace(s.at(i), i);
            ++i;
        }else{
            //find one duplication, record current length and
            //make start index as the duplication position
            result = result > charset.size() ? result : charset.size();
            
            i = iter->second + 1;
            charset.clear();
        }
    }
    
    return result > charset.size() ? result : charset.size();
}

Python Code:

# func: length_of_longest_substring
# goal: find the length of the longest substring which doesn't
#   contain repeating characters
# @param s: the input string
# @return: the length of the longest substring
# complexity: near O(n)
def length_of_longest_substring(s):
    #charset to record current substring
    charset = {}

    i = 0
    result = 0
    while i < len(s):
        #if current character in the substring, record current length
        #and start at the new point, then recounting
        if s[i] in charset:
            result = max(result, len(charset))
            i = charset[s[i]]+1
            charset.clear()
        #else retain the current letter
        else:
            charset[s[i]] = i
            i += 1

    return max(result, len(charset))