Saleh127

Untitled

May 17th, 2020
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int n = 256;
  5.  
  6. string findSubString(string str, string pat)
  7. {
  8. int len1 = str.length();
  9. int len2 = pat.length();
  10. int hash_pat[n] = {0};
  11. int hash_str[n] = {0};
  12. for (int i = 0; i < len2; i++)
  13. hash_pat[pat[i]]++;
  14.  
  15. int start = 0, start_index = -1, min_len = INT_MAX;
  16. int count = 0;
  17. for (int j = 0; j < len1 ; j++)
  18. {
  19. hash_str[str[j]]++;
  20. if (hash_pat[str[j]] != 0 &&
  21. hash_str[str[j]] <= hash_pat[str[j]] )
  22. count++;
  23. if (count == len2)
  24. {
  25. while ( hash_str[str[start]] > hash_pat[str[start]] || hash_pat[str[start]] == 0)
  26. {
  27. if (hash_str[str[start]] > hash_pat[str[start]])
  28. hash_str[str[start]]--;
  29. start++;
  30. }
  31. int len_window = j - start + 1;
  32. if (min_len > len_window)
  33. {
  34. min_len = len_window;
  35. start_index = start;
  36. }
  37. }
  38. }
  39. if (start_index == -1)
  40. {
  41. return "";
  42. }
  43. return str.substr(start_index, min_len);
  44. }
  45. int main()
  46. {
  47. int t;
  48. cin>>t;
  49. while(t--)
  50. {
  51. string str,x="";
  52. int l;
  53. cin>>str;
  54. string pat = "123";
  55. x=findSubString(str,pat);
  56. l=x.size();
  57. cout<<l<<endl;
  58. }
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment