fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<climits>
  4. using namespace std;
  5. string minWindow(string str, string pat){
  6. 	int len1 = str.length();
  7. 	int len2 = pat.length();
  8. 	if(len1<len2){
  9. 		return "";
  10. 	}
  11. 	int hash_str[256] = {0};
  12. 	int hash_pat[256] = {0};
  13. 	for(int i=0;i<len2;i++){
  14. 		hash_pat[pat[i]]++;
  15. 	}
  16. 	int start = 0;
  17. 	int start_idx = -1;
  18. 	int min_len = INT_MAX;
  19. 	int count = 0;
  20. 	for(int j=0;j<len1;j++){
  21. 		hash_str[str[j]]++;
  22. 		if(hash_pat[str[j]]!=0 && hash_str[str[j]]<=hash_pat[str[j]]){
  23. 			count++;
  24. 		}
  25. 		if(count == len2){
  26. 			while(hash_str[str[start]]>hash_pat[str[start]] || hash_pat[str[start]]==0){
  27. 				if(hash_str[str[start]]>hash_pat[str[start]]){
  28. 					hash_str[str[start]]-=1;
  29. 				}
  30. 				start+=1;
  31. 			}
  32. 			int len_window = j-start+1;
  33. 			if(min_len>len_window){
  34. 				min_len = len_window;
  35. 				start_idx = start;
  36. 			}
  37. 		}
  38. 	}
  39. 	if(start_idx == -1){
  40. 		return"";
  41. 	}
  42. 	return str.substr(start_idx,min_len);
  43. }
  44. int main() {
  45. 	string str,pat;
  46. 	getline(cin,str);
  47. 	getline(cin,pat);
  48. 	string ans = minWindow(str,pat);
  49. 	cout<<ans;
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
qwerty asdfgh qazxsw
qas
stdout
copy 
qazxs
https://ideone.com/m2wkfn
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!