C++ 12ms two pointers. Perhaps as hard to read as others but with description on English


  • 0
    P

    A short description of the algorithm since usually it’s not that obvious from the source code how it works and I haven’t seen good enough explanation on English. If you can read Chinese and you understand that description someone mentioned in comment then you probably can ignore my post.

    Below there is description of my implementation of my version of algorithm (12 ms).

    So, at the beginning we init subStrChars array with min int value.
    Then we calculate number of every char in the T string and update corresponding values in the subStrChars.
    So after initialization it contains numeric_limits<int>::min() value for all chars which are not in the T string (so we do not waste time on them while main loop) and number of appearance of every char from the T string .
    For “ABBC” it contains:

    subStrChars[0-64] == numeric_limits<int>::min();
    subStrChars[65(or ‘A’)] == 1;
    subStrChars[66(or ‘B’)] ==2;
    subStrChars[67(or ‘C’)] == 1;

    counter – number of chars from T which we haven’t met. After init count == 4 (2 B + 1 A + 1 C)

    Then we iterate through input S string with two pointers: left and right. Right starts first.
    When right iterator meets char from T we reduce number for this char in the subStrChars and reduce counter.

    “>A<DOBECODEBANC”

    Right meets first A so --subStrChars[65(or ‘A’)] (--subStrChars[cIndx]) and --counter. One nuance: we reduce counter only when subStrChars[cIndx] >= 0. Why do we only decrement when subStrChars[cIndx] >= 0? Because you can meet more As in the S than you actually required by T so do not count those extra As.

    --subStrChars[cIndx];
    if (subStrChars[cIndx] >= 0)
    {
    	counter = max(counter - 1, 0);
    }
    

    Continue incrementing right pointer and reducing counter on every char from T till counter is 0. Once counter == 0 - your right pointer just met all chars in S required by T. Save your left and right pointers.
    I store them in pair<int, int> minSubstr(0, numeric_limits<int>::max());

    if (right - left < minSubstr.second - minSubstr.first)
    {
        minSubstr.first = left;
        minSubstr.second = right;
    }
    
    “>A<DOBE>C<ODEBANC”
      ^Left  ^right
    

    Then start moving left pointer. When it meets char not from T (D or E) you can make your substring shorter and update minSubstr.
    When it meets char from T increment counter and subStrChars[leftCharIndx].
    And again nuance: increment counter only when number of this char in the subStrChars > 0.
    Why? If it's negative - you met more this char than actually required by T so ignore them till subStrChars[currentChar] is > 0.
    Once counter > 0 again you substring between left and right iterators is not complete any more and you found one of the substrings so you need to move your right pointer again to find next char from T to complete your substring to find next substring so on.

    Hopefully this makes implementation a bit easier to understand.

    Code:

    string minWindow(string s, string t) 
    {
        const int exclude = numeric_limits<int>::min();
    	int left = 0, sLength = s.length(), subStrLen = t.length(), counter = 0;
    	pair<int, int> minSubstr(0, numeric_limits<int>::max());
    	vector<int> subStrChars(128, exclude);
    
    	for (char c : t)
    	{
    		if (subStrChars[c] == exclude)
    		{
    			subStrChars[c] = 0;
    		}
    		++subStrChars[c];
    		++counter;
    	}
    
    	for (int right = 0; right < sLength; ++right)
    	{
    		int cIndx = s[right];
    		if (subStrChars[cIndx] == exclude)
    			continue;
    
    		--subStrChars[cIndx];
    		if (subStrChars[cIndx] >= 0)
    		{
    			counter = max(counter - 1, 0);
    		}
    
    		while (counter == 0)
    		{
    			if (right - left < minSubstr.second - minSubstr.first)
    			{
    				minSubstr.first = left;
    				minSubstr.second = right;
    			}
    
    			int leftCharIndx = s[left];
    			if (subStrChars[leftCharIndx] != exclude)
    			{
    				++subStrChars[leftCharIndx];
    				if (subStrChars[leftCharIndx] > 0)
    				{
    					++counter;
    				}
    			}
    			++left;
    		}
    	}
    
    	string res = "";
    	if (minSubstr.second != numeric_limits<int>::max())
    	{
    		res = s.substr(minSubstr.first, minSubstr.second - minSubstr.first + 1);
    	}
    	return res;
    }

Log in to reply
 

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