Simple short C/C++ code 8ms/16ms, O(n) time


  • 1
    S

    tag last repeating characters and get the answer by distances.

    C: 8ms

    int lengthOfLongestSubstring(char* s) {
    	if (s == NULL) return 0;
    	int l = 0;
    	while (s[l] != '\0'){ l++; }
        int m = 0;
        int h[255] = {0};
        int i = 0;
        int o = 0;
        int h_ = 0;
        for (i = 0;i < l; i++){
        	h_ = s[i];
        	if (h[h_] > 0){ o = (o > h[h_]) ? o : h[h_];}
        	h[h_] = i + 1;
        	m = (m > i + 1 - o) ? m : i + 1 - o;
        }
        return m;
    }
    

    C++: 16ms

    int lengthOfLongestSubstring(string s) {
    	int max = 0;
    	int hashTable[255] = {0};
    	int lastOne = 0;
    	for (int i = 0; i < s.size(); i++){
    		int hash = (int)s[i];
    		if (hashTable[hash] > 0){
    			lastOne = std::max(lastOne, hashTable[hash]);
    		}
    		hashTable[hash] = i + 1;
    		max = std::max(max, hashTable[hash] - lastOne);
    	}
    	return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.