Given a string shuffle it such that no consecutive characters are same

#include <iostream>
#include <string.h>
using namespace std;

void shuffle(char* a)
{
 bool done=true;
 int index = 0;
 int n = strlen(a);
 for(int i=0; i<n-1; i++)
 {
  if(a[i] == a[i+1])
  {
   bool found = false;
   for(int j=i+2; j<n; j++)
   {
    if(a[j] != a[i+1])
    {
     char r = a[j];
     a[j] = a[i+1];
     a[i+1] = r;
     found = true;
     break;
    }
   }
   if(!found)
   {
    done = false;
   }
  }
 }
 
 if(!done)
 {
  for(int i=n-1; i>0; i--)
  {
   if(a[i] == a[i-1])
   {
    bool found = false;
    for(int j=i-2; j>=0; j--)
    {
     if(a[j] != a[i-1])
     {
      char r = a[j];
      a[j] = a[i-1];
      a[i-1] = r;
      found = true;
      break;
     }
    }
    if(!found)
    {
     done = false;
     cout << "not possible\n";
    }
   }
  }
 }
}
int main() {
 // your code goes here
 char s[100];
 cin >> s;
 cout << "input: " << s <<endl;
 shuffle(s);
 cout << "output: " << s << endl;
 return 0;
}

input: ABBBCCCCCC
not possible
output: CCACBCBCBC

input: ABBBCCCCC
output: CACBCBCBC

input: ABCDDDDDDABC
output: ADBDCDADBDCD