# Rearrange a string so that all same characters become d distance away!

727 views

Given a string and a positive integer d. Some characters may be repeated in the given string. Rearrange characters of the given string such that the same characters become d distance away from each other. Note that there can be many possible rearrangements, the output should be one of the possible rearrangements.

``````example:
Input:  "abb", d = 2
Output: "bab"
``````
posted May 7, 2014

Check the following code -

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

int main()
{
int count[256]={0},d;
char input[1000];
scanf("%s",input);
scanf("%d",&d);
int ip_size = strlen(input);
char output[ip_size];
int max_count =0;
for(int i=0;i<ip_size;i++)
{
count[input[i]]++;
output[i]='\0';
if(count[input[i]]>max_count)
max_count = count[input[i]];
}

int j=0;int holder=0;
for(int i=0;i<256;i++)
{
holder =j;
if(count[i]>1)
{
while(count[i]>0)
{
output[j] = (char)i;
j=j+d;
count[i]--;
}
}

while(output[holder]!='\0')
{
holder = holder+1;

}
j=holder;
}
for(int i=0;i<256;i++)
{
if(count[i]==1)
{
output[j]=char(i);
count[i]--;
}
while(output[holder]!='\0')
{
holder = holder+1;
}
j=holder;
}

for(int i=0;i<ip_size;i++)
{
if(output[i]!='\0')
printf("%c",output[i]);
else
{printf("\rnot possible\n");break;}
}

printf("\n");

system("pause");
return 0;
}
``````
answer Jun 4, 2014 by anonymous
Similar Questions

Say the given string is `ABC`

Output should be `ABC` `ACB` `BAC` `BCA` `CBA` `CAB`

Given a string, add some characters to the from of it so that it becomes a palindrome.
e.g.
1) If input is "abc" then "bcabc" should be returned.
2) input -> "ab" output -> "bab"
3) input -> "a" output -> "a"

For
e.g 1. "hello how are you" - distance between "hello" and "you" is 3.
e.g 2. "hello how are hello you" - distance is 1
e.g 3. "you are hello" - distance is -1. Order of "hello" and "you" should be preserved.
e.g 4. "hello how are hello" - distance is -1 since "you" did not occur even once.