fork download
copy 
  1.     //... copyright @ASHISH JHA ... _/\_******
  2. /*Licensed under the "THE BEER-WARE LICENSE" (Revision 42):
  3.   Ashish_Jha wrote this file. As long as you retain this notice you
  4.   can do whatever you want with this stuff. If we meet some day, and you think
  5.   this stuff is worth it, you can buy me a beer or coffee in return
  6. */
  7.     #include<bits/stdc++.h>
  8.     using namespace std;
  9.     typedef long long int ll;
  10.     #define MOD 1000000007
  11.     #define pb push_back
  12.     #define pi pair<ll,ll>
  13.     #define pii pair<ll,pair<ll,ll>>
  14.     #define INF 1e10+1
  15.     const ll siz = 150005;
  16.     bool flg=true;
  17.     ll check(string str,ll st,ll end)
  18.     {
  19.         set<char> s;
  20.         ll flg=0;
  21.         for(ll i=st;i<=end;++i)
  22.             {
  23.                     s.insert(str[i]);
  24.             }
  25.         if(s.size()==1)
  26.             return 1;
  27.         else
  28.             return 2;
  29.     }
  30.  
  31.     ll rec(string str,ll low,ll high)
  32.     {
  33.         if(low==high)
  34.             return 0;
  35.         ll ele;
  36.         if(check(str,low,high)==1)
  37.             ele=1;
  38.         else
  39.             ele=0;
  40.         ll mid=(low+high)/2;
  41.         if((low-high)%2==0)
  42.         {
  43.             if(ele==1)
  44.                 return 0;
  45.             else
  46.                 {
  47.                     return INF;
  48.                 }
  49.         }
  50.         else
  51.         {
  52.             if(ele==1)
  53.                 return 0;
  54.             else
  55.                 return (1+min(rec(str,low,mid),rec(str,mid+1,high)));
  56.         }
  57.     }
  58.     ll re=1e5+1;
  59.     int main() {
  60.             ios_base::sync_with_stdio(false);
  61.             cin.tie(NULL);
  62.             cout.tie(NULL);
  63.         //cout<<check("baaa",0,3)<<endl;
  64.          ll t;
  65.          cin>>t;
  66.          while(t--)
  67.          {
  68.              flg=true;
  69.             string str;
  70.             cin>>str;
  71.             ll ans=rec(str,0,str.size()-1);
  72.             if(ans>re)
  73.                 cout<<"-1"<<endl;
  74.             else
  75.                 cout<<ans<<endl;
  76.          }
  77.          return 0;
  78.     }
  79.  
  80.  
  81.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
aacabbaa
aab
stdout
copy 
2
-1
https://ideone.com/RU5UUM
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!