C++ 12 ms beats 96% O(n) solution (one pass, two pointers with map table)


  • 0
    P
    	int str_len = s.length();
    	int l = 0;
    	int len = 0;
    	int max_len = 0;
    	int char_indexes[128]; // vector adds 4 ms. to be faster using array
    	memset(char_indexes, -1, sizeof(char_indexes)); 
        
    	char c = '\0';
    	int prev_indx_of_cur_char = 0;
    	for (int r = 0; r < str_len; ++r)
    	{
    		c = s[r];
    		prev_indx_of_cur_char = char_indexes[c];
    		if (prev_indx_of_cur_char >= l )
    		{
    			l = prev_indx_of_cur_char + 1;
    			len = r - l + 1;
    		}
    		else
    		{
    			++len;
    		}
    		char_indexes[c] = r;
    		max_len = max(len, max_len);
    	}
    
    	return max_len;

Log in to reply
 

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