sundeepblue
4/29/2014 - 7:09 PM

longest substring without repeating characters

longest substring without repeating characters


string longest_substring_without_repeating_chars(const string& s) {
    if(s.empty()) return "";
    int N = s.size();
    
    unordered_map<char, int> hash;
    int i = 0, start = 0;
    int max_len = 1, head = 0;
    while(i < N) {
        char c = s[i];
        if(hash.find(c) == hash.end()) {
            hash[c] = i;
        } else {
            start = hash[c]+1;
            hash[c] = i;
        }
        if(max_len < i - start + 1) {
            head = start;
            max_len = i - start + 1;
        }
        i++;
    }
    return s.substr(head, max_len);
}