Rearrange string

Hard
0/120
Average time to solve is 50m
41 upvotes
Asked in companies
eBayAdobeMicrosoft

Problem statement

You are given a string “S”. Your task is to rearrange the characters of a string “S”, such that it does not contain any two adjacent characters which are the same.

If it is possible to rearrange the string “S”, then print any possible arrangement. else, print “not possible” without quotes.

For Example:

For a string  “qaacde”, This string has two same adjacent characters.
So, one possible way to rearrange the string is “qacade”. Now, this string does not have two adjacent characters that are the same.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains a string S.
Output format : 
For each test case, the output will be “Yes” if you have returned the correct answer, else it will be “No”.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10    
0 <= |S| <= 10^5 

Time Limit: 1 sec
Sample Input 1 :
2 
coding
abaab
Sample Output 1 :
Yes
Yes
Explanation :
For the first test case, the given string is “coding”. This string does not have two adjacent characters that are the same. So if we return “coding", then we will get an output as “Yes”.

For the second test case, the given string is “abaab”. This string has two adjacent characters that are the same i.e. abaab,  So we can rearrange the string as “ababa”.Hence we return “ababa”, then we will get an output as "Yes”.
Sample Input 2 :
1
bbbbbb
Sample Output 2 :
Yes
Explanation :
For the first test case, the given string is “bbbbbb”. No matter how you rearrange characters of string , it will always remain the same as bbbbbb.So we return “not possible” as an answer, then we will get an output as ‘Yes”.
Hint

Think of a solution to check all possible rearrangements

Approaches (4)
Brute force

In this approach, we will generate all the possible rearrangements of the string and check if the current string in our rearrangement does not have any two adjacent characters that are the same. If we can find any string which satisfies our criteria then we will return that string else we will return “not possible”.

 

We can implement the above approach by – 

  1. Generate all permutations of a string.
  2. For each permutation check if this permutation does not have two characters that are the same, if yes then we will return the current permutation else we will move to the next permutation.
  3. If we are not able to find any valid arrangement, then we will return “not possible”.
Time Complexity

O(N*N!), where N is the length of the given string.

 

In the worst case, we will need to generate all permutations that are N! permutations.

Generating and checking the validity of each permutation takes O(N) time.Hence the overall time complexity will be O(N*N!). 

Space Complexity

O(1).

 

In the worst case, a constant space is required.

Code Solution
(100% EXP penalty)
Rearrange string
Full screen
Console