1, Problem description

Here are two strings S and T. please find the shortest substring containing all the characters in T in S. If there is no such substring, the algorithm returns an empty string; If such a substring is found, the answer can be considered to be unique.

2, Violent solution

1. Algorithm

//Violent solution
string fun(string s, string t)
{
	unordered_map<char, int> need;
	unordered_map<char, int> temp;
	//Traverse the string t and record the number of occurrences of each character
	for (char c : t)
		need[c]++;

	int len = s.size()+1, right = 0, left = 0;
	int minLen=t.size();//The length of string T is also the minimum length of the shortest substring
	for (int i = 0;i < s.size();i++)
	{
		for (int j = i + 1;j < s.size();j++)
		{
			if (j - i >= minLen)
			{//All characters in t can be included only if the substring length is greater than or equal to the length of T
				int index = 0;
				int count = 0;
				while (index < t.size())
				{//Traverse the string t to ensure that the substring contains all the characters in t				
					string tempS = s.substr(i, j - i);

					//Use temp to record the characters in the current substring tempS for comparison with the characters in t
					for (char c : tempS)
						temp[c]++;

					char f = t[index];
					index++;
					if (temp.count(f))					
						count++;										
					else
						break;//If the substring tempS does not contain the character f, the current substring is invalid and the middle section loops
					temp.clear();//Clear all elements in temp to prepare for saving the next substring
				}

				//count == minLen indicates that the current substring s.substr(left,j-i) contains all characters in t, and the substring will be updated if the length of the current substring is less than the length of the previous substring
				if (count == minLen && (j-i<len))
				{
					len = j - i;
					left = i;
					right = j;
					//cout << "left=" << left << "  right" << right << " len" << len << endl;
					break;//The second cycle is interrupted here, because the length of substring s.substr(left,j-i) must be less than the length of substring s.substr(left,j+1-i)
				}
			}
		}
	}

	return len == s.size() + 1 ? " " : s.substr(left, len);
}

``

2. Analysis

The two-layer for loop traverses the string s to continuously obtain the substring s.substr(i,j-1) in order to check whether the substring contains all the characters in t (that is, the function of while in the second layer loop), and select the substring with the smallest length among all qualified substrings (if there are two or more minimum strings, select the first substring as the answer). Important parts of the algorithm have been commented in the code. If you still don't understand, please leave a message and talk about it, and I will reply as soon as possible.
The idea of the algorithm is direct and simple, and three-layer loop is used, and the time complexity must be greater than O(N^2).
Note: duplicate characters cannot appear in string t

3, Sliding window algorithm

1. Algorithm idea

1) : we use the left and right pointer techniques in the double pointer in the string s, initialize left=right=0, and call the index left closed right open interval * * [left,right) as a window
2) : continuously increase the right pointer to expand the window [left, right] until the string in the window meets the requirements (including all characters in t).
3) : at this time, stop adding right, and continue to increase the left pointer to narrow the window [left,right) * *, until the characters in the window no longer meet the requirements. At the same time, update the results every time you add left.
4) : repeat steps 2 and 3 until right reaches the end of the string s.

2. Algorithm code

//Move window function
string minWindow(string s, string t)
{
	unordered_map<char, int> need, window;

	//Traverse the string t and record the number of occurrences of each character
	for (char c : t)
		need[c]++;
	
	int left = 0, right = 0;
	int valid = 0;

	//Record the starting index and length of the minimum coverage string
	int start = 0, len = s.size()+1;

	while (right < s.size())
	{
		char c = s[right];
		right++;//Expand window right

		if (need.count(c))
		{
			window[c]++;

			if (window[c] == need[c])			
				valid++;//If the corresponding values of the current character in window and need are consistent, the valid value will be increased by one				
		}

		//valid == need.size() indicates that all characters in need have been included in the current form
		while (valid == t.length())
		{//Enter the loop until the form window does not fully contain all the characters in need
			int formedSize=right-left;
			if (right - left< len)
			{			
				start = left;//Update window start bit
				len = right - left;//Update window size
			}

			char c = s[left];//Extract the first character of the current window
			left++;//Move left and right of window

			if (need.count(c))
			{
				if (window[c]==need[c])
					valid--;//If the corresponding values of the current character in window and need are consistent, the valid value will be reduced by one
				window[c]--;//If the current character exists in need(t), the corresponding value in window will be reduced by one
			}
		}
	}

	//cout << endl;
	//cout << "start=" << start <<"  len="<< len<< endl;
	return len == s.size()+1 ? "" : s.substr(start, len);
}

3. Simple analysis

In the algorithm, only one loop of while (valid == t.length()) is nested in while (right < s.size()), which belongs to two-tier loop. The time complexity of the algorithm is obviously smaller than that of the violent solution.
Note: the sliding window algorithm is learned in section 1.7.1 of the book < < labuladong's algorithm speculation > >. The main code is basically the same as that in the book, only a small part has been modified and some comments have been added.