Advertisement
Guest User

Untitled

a guest
May 30th, 2017
1,874
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //#define debug(...) printf( __VA_ARGS__ )
  5. #define debug(...) /****nothing****/
  6.  
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define pb push_back
  10. #define mem(arr,val) memset(arr,val,sizeof(arr))
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define F first
  14. #define S second
  15. #define sz(x) (int)(x).size()
  16. #define nopos string::npos
  17. #define fr(i,a,b) for(i=a;i<=b;i++)
  18. #define frn(i,a,b) for(i=a;i>=b;i--)
  19.  
  20.  
  21. int n,sz,cnt,i,j;
  22. set<char> data;
  23. char str[123456];
  24.  
  25. int main()
  26. {
  27.  
  28. while(cin>>n)
  29. {
  30. scanf("%s",str+1);
  31.  
  32. int ans=n+1;
  33. data.clear();
  34.  
  35. for(i=1;i<=n;i++)
  36. data.insert(str[i]);
  37.  
  38. cnt=data.size(); // all types of pokemon in string str
  39.  
  40. for(i=1;i<=n;i++)
  41. {
  42. int low=i-1 , high=n+1;
  43. while(high-low>1)
  44. {
  45. int mid=(high+low)/2;
  46. data.clear();
  47.  
  48. for(j=i;j<=mid;j++)
  49. data.insert(str[j]); //to evaluate : how many distinct character from i index to mid index
  50.  
  51. if(data.size()>=cnt)
  52. high=mid;
  53. else
  54. low=mid;
  55. }
  56.  
  57. if(high!=n+1) // we got a segment from i to high where number of distinct characters are equal to cnt
  58. {
  59. ans=min(ans,high-i+1);
  60. }
  61. }
  62.  
  63. cout<<ans<<'\n';
  64.  
  65. }
  66.  
  67.  
  68.  
  69. return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement