Rearrange string
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.

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

Question

Rearrange string

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.

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

Accepted Answer

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 –

Generate all permutations of a string.
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.
If we are not able to find any valid arrangement, then we will return “not possible”.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a constant space is required.

Time Complexity: OtherExplanation:

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!).

Accepted Answer

Heap Approach

The idea is here to store the frequency of each character in a hashmap and then build a max heap of pairs containing the frequency of character and character.

We will always pick the highest frequency character that is not the same as the previously picked character from the max heap and add the picked character to the answer.

Steps :

Declare an empty string as an ANSWER.
Store frequency of each character in a hashmap or array, key as a character, and value as its frequency.
Build a max heap of pairs where each pair contains the frequency of character as a key and character as value.
Declare a variable PREV to store the previously picked element and initialize it with -1.
Run a loop until the max heap is not empty and do
1. Pop the top element from max heap and add the character of the popped element to ANSWER.
2. Decrease frequency of popped element by 1.
3. Push the previous element back to max heap if its frequency is greater than 0.
4. Make a popped element as the previous element for the next iteration.
If the length of the original string and ANSWER is not equal then return “not possible”.
Else return the ANSWER.

Space Complexity: O(n)Explanation:

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

In the worst case, a constant space is required for storing frequencies as we are creating array of size 26, and the max heap requires O(N) space.Hence the overall space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

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

In the worst case, calculating frequency requires O(N) time, and generating max heap requires O(N * log(N)) time. Also accessing the top element from max heap requires O(log(N)) time and we need to access O(N) elements, so it will require around O(N * log(N)) time.

So, O(N) + O(N * log(N)) + O(N * log(N)) = O(N * log(N)). Hence the overall complexity will be O(N * log(N)).

Java (SE 1.8)

/*

	Time Complexity  : O(N * log(N))

	Space Complexity : O(N)



	Where N is the total number of elements in the string.

*/



import java.util.PriorityQueue;

import java.util.Comparator;



class Pair {

    T1 key;

    T2 value;



    public Pair(T1 a, T2 b) {

        key = a;

        value = b;

    }

}



class ThePairComparator implements Comparator> {

    public int compare(Pair p1, Pair p2) {

        return p2.key - p1.key;

    }

}



public class Solution {



    public static String reArrangeString(String s) {



        // Store frequency of all characters in hash.

        int[] hash = new int[26];



        for (int index = 0; index < s.length(); index++) {

            hash[s.charAt(index) - 'a']++;

        }



        // Declare max heap.

        PriorityQueue> maxHeap = new PriorityQueue<>(new ThePairComparator());



        // Build max heap using frequency of characters.

        for (int index = 0; index < 26; index++) {

            if (hash[index] == 0) {

                continue;

            }

            maxHeap.add(new Pair<>(hash[index], (char) ('a' + index)));

        }



        // Declare answer to store result.

        StringBuilder answer = new StringBuilder();



        // Declare prev to store previous character store in answer.

        Pair prev = new Pair<>(-1, '@');



        // Run a loop until max heap is not empty.

        while (!maxHeap.isEmpty()) {



            // Get top item from max heap

            Pair currMax = maxHeap.poll();



            // Decrease frequency of top item of heap from 1 and character of top item to answer.

            currMax.key--;



            answer.append(currMax.value);



            // Push previous character back to heap if its frequency > 0.

            if (prev.key > 0) {

                maxHeap.add(prev);

            }



            // Make current most frequent as previous character.

            prev = currMax;

        }



        // Check if size of answer is equal to s or not.

        if (answer.length() != s.length()) {

            return "not possible";

        }



        return answer.toString();

    }

}

C++ (g++ 5.4)

/*

	Time Complexity  : O(N * log(N))

	Space Complexity : O(N)



	Where N is the total number of elements in the string.

*/



#include 



string reArrangeString(string &s)

{

	int n = s.size();

	vector hash(26, 0);



	// Store frequency of all characters in hash.

	for (char character : s)

	{

		hash[character - 'a']++;

	}



	// Declare max heap.

	priority_queue> maxHeap;



	// Declare prev to store previous character store in answer.

	pair prev = {-1, '@'};



	// Build max heap using frequency of characters

	for (int character = 0; character < 26; character++)

	{

		if (hash[character] == 0)

			continue;

		maxHeap.push({hash[character], 'a' + character});

	}



	// Declare answer to store result.

	string answer = "";



	// Run a loop until max heap is not empty.

	while (maxHeap.empty() == false)

	{



		// Get top item from max heap.

		pair curMax = maxHeap.top();

		maxHeap.pop();



		// Decrease frequency of top item of heap from 1 and character of top item to answer.

		curMax.first--;

		answer.push_back(curMax.second);



		// Push previous character back to heap if its frequency > 0.

		if (prev.first > 0)

		{

			maxHeap.push(prev);

		}



		// Make current most frequent as previous character.

		prev = curMax;

	}



	string notValid = "not possible";



	// Check if size of answer is equal to s or not.

	if (answer.size() != s.size())

	{

		return notValid;

	}

	return answer;

}

Python (3.5)

'''
	Time Complexity  : O(N * log(N))
	Space Complexity : O(N)

	Where N is the total number of elements in the string.
'''

import heapq

def reArrangeString(s):
    
    # Store frequency of all characters in hash.
    hashValue = [0] * 26
    n = len(s)
    
    for index in range(n):
        hashValue[ord(s[index]) - ord('a')] += 1
        
    # Declare max heap.
    maxHeap = []
    
    # Build max heap using frequency of characters
    for index in range(26):
        if hashValue[index] == 0:
            continue
        heapq.heappush(maxHeap, (-hashValue[index], chr(ord('a') + index)))
        
    # Declare answer to store result.
    answer = ""
    
    # Declare prev to store previous character store in answer.
    prev = (-1, '@')
    # Run a loop until max heap is not empty.
    while len(maxHeap) > 0:
        # Get top item from max heap.
        currMax = heapq.heappop(maxHeap)
        # Decrease frequency of top item of heap from 1 and character of top item to answer.
        temp = -currMax[0] - 1
        currMax = (temp, currMax[1])
        
        answer += currMax[1]
        # Push previous character back to heap if its frequency > 0.
        if prev[0] > 0:
            heapq.heappush(maxHeap, (-prev[0], prev[1]))
        
        # Make current most frequent as previous character.
        prev = currMax
        
    # Check if size of answer is equal to s or not.
    if len(answer) != len(s):
        return "not possible"
        
    return answer

Accepted Answer

Sorting Approach

The idea is here to sort the string based on the frequency of characters and then merge characters one by one from the front and middle of the string using left and right pointers.

Steps :

Declare an empty string as an answer.
Store the frequency of each character in a hashmap.
Sort the given string based on the frequency of characters.
Initialize left and right pointer as LEFT = 0 and RIGHT = (N – 1)/2 + 1, where N is length of string.
Run a loop until LEFT<=(N-1)/2 and do :
1. Add S[LEFT] to answer and increment LEFT by 1 i.e. do LEFT = LEFT +1.
2. If RIGHT < N then, Add S[RIGHT] to ANSWER and increment RIGHT by 1 i.e. do RIGHT = RIGHT + 1.
Check if the ANSWER has any two adjacent characters that are the same, if yes then return “not possible” else return an ANSWER.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a hash array requires O(26) space which is constant space .Hence overall space complexity will be O(1).

Time Complexity: O(n)Explanation:

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

In the worst case, the check function will require O(N) time, and sorting requires O(26*log(26)) time as there are only 26 elements i.e. a to z which we are required to sort. Calculating the hash array requires O(N) time. Building an answer array requires O(N) time.So, O(N) + O(26*log(26)) + O(N) + O(N) = O(N). Hence the overall complexity will be O(N).

Python (3.5)

'''
	Time Complexity  : O(N)
	Space Complexity : O(1)

	Where N is the total number of elements in the string.
'''

def check(s):
    n = len(s)
    
    for i in range(1, n):
        if s[i] == s[i - 1]:
            return False
            
    return True

def reArrangeString(s):
    
    n = len(s)
    
    if n == 0:
        return s
    
    # Store frequency of all characters in hash.
    hashValue = [0] * 26
    
    for index in range(n):
        hashValue[ord(s[index]) - ord('a')] += 1
        
    store = []
    
    # Use store to sort characters based on frequency.
    for character in range(26):
        store.append((hashValue[character], chr(ord('a') + character)))
        
    store.sort(key=lambda x: (-x[0], x[1]))
    
    sortedS = ""
    
    for Pair in store:
        for i in range(Pair[0]):
            sortedS += Pair[1]
            
    # Use to pointers left and right to merger characters from front and middle of sorted string.
    left = 0
    right = (n - 1) // 2 + 1
    s = sortedS
    
    answer = ""
    
    while left <= (n - 1) // 2:
        answer += s[left]
        
        if right < n:
            answer += s[right]
            
        left += 1
        right += 1
        
        
    notValid = "not possible"
    
    # If string still contains two same adjacent characters then return not possible.
    if not check(answer):
        return notValid
        
    return answer

C++ (g++ 5.4)

/*

	Time Complexity  : O(N)

	Space Complexity : O(1)



	Where N is the total number of elements in the string.

*/



#include 



bool check(string &s)

{

	int n = s.size();



	for (int i = 1; i < n; i++)

	{

		if (s[i] == s[i - 1])

		{

			return false;

		}

	}

	return true;

}



string reArrangeString(string &s)

{

	vector> store;

	int n = s.size();

	vector hash(26, 0);



	// Store frequency of all characters in hash array.

	for (char character : s)

	{

		hash[character - 'a']++;

	}



	// Use store to sort characters based on frequency.

	for (int character = 0; character < 26; character++)

	{

		store.push_back({hash[character], 'a' + character});

	}



	// Sort the frequency of characters in decreasing order.

	sort(store.rbegin(), store.rend());

	s = "";

	// Revert back to all characters in string such that characters having high frequency will come first.

	for (auto &pair : store)

	{



		for (int i = 0; i < pair.first; i++)

		{

			s.push_back(pair.second);

		}

	}



	// Use to pointers left and right to merger characters from front and middle of sorted string.

	int left = 0, right = (n - 1) / 2 + 1;

	string answer = "";



	while (left <= (n - 1) / 2)

	{

		answer.push_back(s[left]);

		if (right < n)

		{

			answer.push_back(s[right]);

		}

		left++;

		right++;

	}



	string notValid = "not possible";



	// If string still contains two same adjacent characters then return not possible.

	if (check(answer) == false)

	{

		return notValid;

	}

	return answer;

}

Java (SE 1.8)

/*

	Time Complexity  : O(N)

	Space Complexity : O(1)



	Where N is the total number of elements in the string.

*/



import java.util.Collections;

import java.util.Comparator;

import java.util.ArrayList;



class TheKeyComparator implements Comparator {



    public int compare(Pair p1, Pair p2) {

        return p2.key - p1.key;

    }

}



class Pair {

    int key;

    char value;



    public Pair(int a, char b) {

        key = a;

        value = b;

    }

}



public class Solution {



    public static String reArrangeString(String s) {

        int n = s.length();



        if (n == 0) {

            return s;

        }



        // Store frequency of all characters in hash.

        int[] hash = new int[26];



        for (int index = 0; index < s.length(); index++) {

            hash[s.charAt(index) - 'a']++;

        }



        ArrayList store = new ArrayList<>();



        // Use store to sort characters based on frequency.

        for (int character = 0; character < 26; character++) {

            store.add(new Pair(hash[character], (char) ('a' + character)));

        }



        Collections.sort(store, new TheKeyComparator());



        StringBuilder sortedS = new StringBuilder();



        // Revert back to all characters in string such that characters having high frequency will come first.

        for (Pair Pair : store) {



            for (int i = 0; i < Pair.key; i++) {

                sortedS.append(Pair.value);

            }



        }



        // Use to pointers left and right to merger characters from front and middle of sorted string.

        int left = 0, right = (n - 1) / 2 + 1;

        s = sortedS.toString();



        StringBuilder answer = new StringBuilder();

        while (left <= (n - 1) / 2) {



            answer.append(s.charAt(left));



            if (right < n) {

                answer.append(s.charAt(right));

            }

            left++;

            right++;

        }

        String notValid = "not possible";



        // If string still contains two same adjacent characters then return not possible.

        if (!check(answer.toString())) {

            return notValid;

        }

        return answer.toString();



    }



    // Function to check whether string contains two adjacent characters that are same.

    private static boolean check(String s) {

        int n = s.length();



        for (int i = 1; i < n; i++) {

            if (s.charAt(i) == s.charAt(i - 1)) {

                return false;

            }

        }

        return true;



    }

}

Accepted Answer

Hashing Approach

The idea here is to store the frequency of each character of a string in a frequency array.

Let’s consider the following two observations:

We can fill the same characters in either even positions or odd positions of string.
The order of filling characters does not matter except for the highest frequency character.
Let us denote the length of the string as N. If the frequency of the highest frequency element in the string is greater than (N+1)/2 then we cannot generate a string that does not have any two same characters.

So we will fill maximum frequency characters first in even positions and then remaining characters at odd positions. If all even positions are filled then we will start filling from odd positions.

Steps :

Declare an empty string as an ANSWER.
Declare an array of size 26 as HASH[26] to store the frequency of each character.
Store frequency of each character of a string in HASH.
Calculate the maximum frequency character using HASH. Let us denote it by MAX_FREQUENCY_CHARACTER.
If HASH[MAX_FREQUENCY_CHARACTER] > (N+1)/2 then return “not possible”.
Store all characters of MAX_FREQUENCY in even positions of ANSWER.
Store remaining characters in even position of ANSWER and if all even positions are filled then use odd positions to store characters in ANSWER.
Return ANSWER.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, we are using an extra array hash which requires O(26) additional space i.e O(1). Hence the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

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

In the worst case, calculating the frequency of each character takes O(N) time and filling characters at even and odd positions also take O(N) time. Hence overall time complexity is O(N).

C++ (g++ 5.4)

/*

	Time Complexity  : O(N)

	Space Complexity : O(1)



	Where N is the total number of elements in the string.

*/



string reArrangeString(string &s)

{

	int n = s.size();



	// Store frequency of characters in hash array.

	vector hash(26, 0);

	for (char character : s)

	{

		hash[character - 'a']++;

	}



	// Calculate most frequent character in string.

	char mostFrequentCharacter;

	int maxFrequency = 0;

	for (int character = 0; character < 26; character++)

	{

		if (hash[character] > maxFrequency)

		{

			mostFrequentCharacter = 'a' + character;

			maxFrequency = hash[character];

		}

	}



	// If max frequency element > (n+1)/2 then return not possible.

	string notValid = "not possible";

	if (maxFrequency > (n + 1) / 2)

	{

		return notValid;

	}



	// Assign max frequency element to all even positions.

	string answer = s;

	int currentIndex = 0;

	while (maxFrequency > 0)

	{

		answer[currentIndex] = mostFrequentCharacter;

		currentIndex += 2;

		maxFrequency--;

	}

	hash[mostFrequentCharacter - 'a'] = 0;



	// Assign remaining characters to even positions and if all even positions are filled then use odd positions.

	for (int character = 0; character < 26; character++)

	{



		while (hash[character] > 0)

		{

			// If even positions are filled then set current index to 1 and start filling odd positions.

			if (currentIndex >= n)

			{

				currentIndex = 1;

			}



			hash[character]--;



			answer[currentIndex] = 'a' + character;

			currentIndex += 2;

		}

	}

	return answer;

}

Python (3.5)

'''
	Time Complexity  : O(N)
	Space Complexity : O(1)

	Where N is the total number of elements in the string.
'''

def reArrangeString(s):
    
    n = len(s)
    
    if n == 0:
        return s
    
    # Store frequency of all characters in hash.
    hashValue = [0] * 26
    
    for index in range(n):
        hashValue[ord(s[index]) - ord('a')] += 1
        
    # Calculate most frequent character in string.
    mostFrequentCharacter = ""
    maxFrequency = 0
    for character in range(26):
        if hashValue[character] > maxFrequency:
            mostFrequentCharacter += (chr(ord('a') + character))
            maxFrequency = hashValue[character]
            
    mostFrequentCharacter = mostFrequentCharacter[-1]
    # If max frequency element > (n+1)/2 then return not possible.
    notValid = "not possible"
    if maxFrequency > (n + 1) // 2:
        return notValid
        
    # Assign max frequency element to all even positions.
    answer = s
    currentIndex = 0
    
    while maxFrequency > 0:
        answer = answer[ : currentIndex] + mostFrequentCharacter[:] + answer[currentIndex + 1 : ]
        currentIndex += 2
        maxFrequency -= 1
        
    hashValue[ord(mostFrequentCharacter) - ord('a')] = 0
    
    # Assign remaining characters to even positions and if all even positions are filled then use odd positions.
    for character in range(26):
        
        while hashValue[character] > 0:
            # If even positions are filled then set current index to 1 and start filling odd positions.
            if currentIndex >= n:
                currentIndex = 1
                
            hashValue[character] -= 1
            
            answer = answer[ : currentIndex] + chr(ord('a') + character) + answer[currentIndex + 1 : ]
            currentIndex += 2
            
    return "".join(answer)

Java (SE 1.8)

/*

	Time Complexity  : O(N)

	Space Complexity : O(1)



	Where N is the total number of elements in the string.

*/



public class Solution {



    public static String reArrangeString(String s) {



        int n = s.length();

        if (n == 0) {

            return s;

        }



        // Store frequency of all characters in hash.

        int[] hash = new int[26];



        for (int index = 0; index < s.length(); index++) {

            hash[s.charAt(index) - 'a']++;

        }



        // Calculate most frequent character in string.

        char mostFrequentCharacter = ' ';

        int maxFrequency = 0;

        for (int character = 0; character < 26; character++) {

            if (hash[character] > maxFrequency) {

                mostFrequentCharacter = (char) ('a' + character);

                maxFrequency = hash[character];

            }

        }



        // If max frequency element > (n+1)/2 then return not possible.

        String notValid = "not possible";

        if (maxFrequency > (n + 1) / 2) {

            return notValid;

        }



        // Assign max frequency element to all even positions.

        char[] answer = new char[s.length()];



        int currentIndex = 0;



        while (maxFrequency > 0) {

            answer[currentIndex] = mostFrequentCharacter;

            currentIndex += 2;

            maxFrequency--;

        }



        hash[mostFrequentCharacter - 'a'] = 0;



        // Assign remaining characters to even positions and if all even positions are filled then use odd positions.

        for (int character = 0; character < 26; character++) {



            while (hash[character] > 0) {

                // If even positions are filled then set current index to 1 and start filling odd positions.

                if (currentIndex >= n) {

                    currentIndex = 1;

                }



                hash[character]--;



                answer[currentIndex] = (char) ('a' + character);

                currentIndex += 2;

            }

        }



        StringBuilder ans = new StringBuilder();

        for (Character x : answer) {

            ans.append(x);

        }

        return ans.toString();

    }



}

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:

Input format :

Output format :

Note:

Constraints :

Top Microsoft Corporation SDE-2 interview questions & answers

Popular interview questions of SDE-2

Top HR questions asked in Microsoft Corporation SDE-2