a53

min_subsir

a53
Nov 8th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4. const int MAX_CHARS=10001;
  5. string str;
  6.  
  7. string findSubString(string str)
  8. {
  9. int n=str.length();
  10. int dist_count=0;
  11. bool visited[MAX_CHARS]={false};
  12. for(int i=0;i<n;++i)
  13. if(visited[(int)str[i]]==false)
  14. visited[(int)str[i]]=true,++dist_count;
  15. int start=0,start_index=-1,min_len=INT_MAX;
  16. int countc=0;
  17. int curr_count[MAX_CHARS]={0};
  18. for(int j=0;j<n;++j)
  19. {
  20. ++curr_count[(int)str[j]];
  21. if(curr_count[(int)str[j]]==1)
  22. ++countc;
  23. if(countc==dist_count)
  24. {
  25. while(curr_count[(int)str[start]]>1)
  26. {
  27. if(curr_count[(int)str[start]]>1)
  28. --curr_count[(int)str[start]];
  29. ++start;
  30. }
  31. int len_window=j-start+1;
  32. if(min_len>len_window)
  33. min_len=len_window,start_index=start;
  34. }
  35. }
  36. return str.substr(start_index,min_len);
  37. }
  38.  
  39. int main()
  40. {
  41. cin>>str;
  42. str=findSubString(str);
  43. cout<<str.length();
  44. return 0;
  45. }
Add Comment
Please, Sign In to add comment