fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dpr[100100],dpb[100100];
  4. //dpr[i] denotes str[0....i] ending with r and having alternating characters.
  5. //dpb[i] denotes str[0....i] ending with b and having alternating characters.
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     cout.tie(0);
  10.     string str;
  11.     int n;
  12.     cin>>n;
  13.     cin>>str;
  14.     if(n==1){   //if string length is 1
  15.         cout<<0<<"\n";
  16.         exit(0);
  17.     }
  18. 	//computing solution for the first two characters str[0] & str[1].
  19.     if(str[0]==str[1]){  //if characters are same. 
  20.         if(str[0]=='r')   
  21.             dpb[0]=1;  
  22.         else
  23.             dpr[0]=1;
  24.         dpr[1]=1;
  25.         dpb[1]=1;
  26.     }
  27.     else{                //if characters are different.
  28.         if(str[0]=='r'){  
  29.             dpb[0]=1;
  30.             dpr[1]=1;
  31.         }
  32.         else{
  33.             dpr[0]=1;
  34.             dpb[1]=1;
  35.         }
  36.     }
  37.     for(int i=2;i<n;i++){
  38.         if(str[i]=='r'){    //this if-else computes solution for coloring str[i] and str[i-1]
  39.             dpr[i]=dpb[i-1];
  40.             dpb[i]=1+dpr[i-1];
  41.         }
  42.         else{
  43.             dpr[i]=1+dpb[i-1];
  44.             dpb[i]=dpr[i-1];
  45.         }
  46.         if(str[i]!=str[i-1])  //this if-else checks if str[i] and str[i-1] are different, if they are, it checks for swap case.
  47.             if(str[i]=='b')
  48.                 dpr[i]=min(dpr[i],1+dpr[i-2]);
  49.             else
  50.                 dpb[i]=min(dpb[i],1+dpb[i-2]);
  51.     }
  52.     cout<<min(dpr[n-1],dpb[n-1])<<"\n"; //computes final solution
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4244KB
comments (?)
stdin 
5
bbbbb
stdout 
2
https://ideone.com/RYOQkS
language:
C++14 (gcc 8.3)
created:
8 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!