Statement

Given a string, str, rearrange it so that any two adjacent characters are not the same. If such a reorganization of the characters is possible, output any possible valid arrangement. Otherwise, return an empty string.

Constraints:

  • 1≤1\leq str.length ≤500\leq500
  • Input string consists of lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to generate all possible permutations of the given string and check if the generated string is a valid arrangement or not. If any permutation satisfies the condition of a valid reorganization of the string, return that permutation of the input string. If no permutation is a valid reorganization of the string, return an empty string.

The number of possible permutations for a string of length nn is n!n!, and it might require iterating through the nn characters to construct each permutation. Therefore, it will take O(n!×n)O(n! \times n) time to generate all these permutations. Then, for each permutation, we need to check whether it satisfies the condition of having no adjacent characters that are the same. Checking this condition requires iterating through the permutation once, which takes O(n)O(n) time. Therefore, the overall time complexity of this naive approach is O((n!×n)×n)O((n! \times n)\times n).

Optimized solution using top kk elements

The key idea behind this efficient solution is to prioritize characters’ arrangement by frequency using a max-heap. This way, the character with the highest frequency is always processed first. By popping the most frequent character from the heap and placing it in the result string, we temporarily hold it aside to prevent it from being placed next to itself. By doing this, we avoid having the same character appear consecutively.

Let’s use this technique to reorganize the input string. The max-heap will store characters along with their frequencies, ensuring the character with the highest frequency is always at the root. By building the order from the most frequent to the least frequent character, we aim to find a valid reorganization of the string. If we cannot achieve this, it means that it’s impossible to rearrange the string.

The illustration below shows the whole process:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

First, we calculate the frequency of the characters in the input string. We store each character as a key in a hash map and set its value to the frequency of its occurrence in the string.

import java.util.*;
class Reorganize {
    public static String reorganizeString(String str) {
        // initializing the hash map
        Map <Character, Integer> charCounter = new HashMap <> ();
        // Calculate the frequency of characters in string and store counts
        // of each character along with the character itself in hash map.
        for (char c: str.toCharArray()) {
            int freq = charCounter.getOrDefault(c, 0) + 1;
            charCounter.put(c, freq);
        }
        return charCounter.toString();
    }
    public static void main(String args[]) {
        String[] inputs = {
            "programming",
            "hello",
            "fofjjb",
            "abbacdde",
            "aba",
            "awesome"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput string: \"" + inputs[i] + "\"");
            System.out.println("\tCharacter counts: " + reorganizeString(inputs[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reorganize String

After getting all the characters and their respective frequencies, we initialize the heap to provide quick access to the most frequently occurring characters in the string. Since some languages, such as Python, don’t have built-in max-heap functionality, we store the frequencies in a heap in such a way that will serve our purpose.

Note: We’ll implement the heap using the PriorityQueue class.

We first iterate through the hash map and store the negative count of each character and the character itself in a heap. The reason for storing the negative count of each character is that when we pop characters from the heap, the heap will return the character with the maximum frequency.

import java.util.*;
class Reorganize {
    public static String reorganizeString(String str) {
        // initializing the hash map
        Map <Character, Integer> charCounter = new HashMap <> ();
        
        // Calculate the frequency of characters in string and store counts
        // of each character along with the character itself in hash map.
        for (char c: str.toCharArray()) {
            int freq = charCounter.getOrDefault(c, 0) + 1;
            charCounter.put(c, freq);
        }
        // initializing max heap
        PriorityQueue <Map.Entry<Character, Integer>> maxFreqChars = new PriorityQueue <Map.Entry<Character, Integer>> (
            (item1, item2) -> item2.getValue() - item1.getValue());
        // store all characters with their frequencies to the max heap
        maxFreqChars.addAll(charCounter.entrySet());
        System.out.println(maxFreqChars);
        return maxFreqChars.toString();
    }
    public static void main(String args[]) {
        String[] inputs = {
            "programming",
            "hello",
            "fofjjb",
            "abbacdde",
            "aba",
            "awesome"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput string: \"" + inputs[i] + "\"");
            System.out.print("\tCharacter frequencies as a max-heap: ");
            reorganizeString(inputs[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reorganize String

Now, we take two variables, previous and result. The previous variable stores the previous character that we used so that we don’t use that character again. The result variable stores the final reorganized string.

The character with the highest frequency will always be at the root of our heap. We keep popping characters from the top of the heap to add them to the result string.

When we add a character to the result string, we won’t push this character back onto the heap right away, even if its frequency of occurrence is greater than 00. Instead, we add it back to the heap in the next iteration. The reason is that we want to ensure that the same characters don’t appear adjacent to each other in the result string. Therefore, we store the current character along with its frequency of occurrence in previous for use in the next iteration.

import java.util.*;
class Reorganize {
    public static String reorganizeString(String str) {
        // initializing the hash map
        Map <Character, Integer> charCounter = new HashMap <> ();
        // Calculate the frequency of characters in string and store counts
        // of each character along with the character itself in hash map.
        for (char c: str.toCharArray()) {
            int freq = charCounter.getOrDefault(c, 0) + 1;
            charCounter.put(c, freq);
        }
        
        // initializing the max heap
        PriorityQueue <Map.Entry <Character, Integer>> maxFreqChar = new PriorityQueue <Map.Entry <Character, Integer>> (
            (item1, item2) -> item2.getValue() - item1.getValue());
        // store all characters with their frequencies to the max heap
        maxFreqChar.addAll(charCounter.entrySet());
        // initializing variables
        Map.Entry <Character, Integer> previous = null;
        StringBuilder result = new StringBuilder(str.length());
        while (!maxFreqChar.isEmpty() || previous!=null) {
            
            Map.Entry < Character, Integer > currentEntry = maxFreqChar.poll();
            // decrement the character count, as we've now used one occurrence of it
            int count=currentEntry.getValue()-1;
            result.append(currentEntry.getKey());
            // pushing the char back to heap
            if(previous!=null){
                maxFreqChar.add(previous);
                previous=null;
            }
            
            // setting previous to the most recent used char
            if(count != 0){
                previous = new AbstractMap.SimpleEntry<>(currentEntry.getKey(), count);      
            }
        }
        return result.toString();
    }
    public static void main(String args[]) {
        String[] inputs = {
            "programming",
            "hello",
            "fofjjb",
            "abbacdde",
            "aba",
            "awesome",
            "aab"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput string: \"" + inputs[i] + "\"");
            System.out.println("\tReorganized string: \"" + reorganizeString(inputs[i])+ "\"");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reorganize String

So far, our solution handles almost all the cases, but it’s still incomplete. It does not handle the strings for which reorganization is not possible like aaab. This string cannot be reorganized.

To handle these types of cases, we add an extra condition to our loop. If our heap is empty and the previous variable is non-empty, that means we get to a point where we cannot generate any solution because no valid reordering of the string exists. Therefore, an empty string is returned.

import java.util.*;
class Reorganize {
    public static String reorganizeString(String str) {
        // initializing the hash map
        Map <Character, Integer> charCounter = new HashMap <> ();
        
        // Calculate the frequency of characters in string and store counts
        // of each character along with the character itself in hash map.
        for (char c: str.toCharArray()) {
            int freq = charCounter.getOrDefault(c, 0) + 1;
            charCounter.put(c, freq);
        }
        // initializing the max heap
        PriorityQueue <Map.Entry <Character, Integer>> maxFreqChar = new PriorityQueue <Map.Entry <Character, Integer>> (
            (item1, item2) -> item2.getValue() - item1.getValue());
        // store all characters with their frequencies to the max heap
        maxFreqChar.addAll(charCounter.entrySet());
        // initializing variables
        Map.Entry <Character, Integer> previous = null;
        StringBuilder result = new StringBuilder(str.length());
        while (!maxFreqChar.isEmpty() || previous!=null) {
            if (previous != null && maxFreqChar.isEmpty())
                return "";
            
            Map.Entry <Character, Integer> currentEntry = maxFreqChar.poll();
            // decrement the character count, as we've now used one occurrence of it
            int count=currentEntry.getValue()-1;
            result.append(currentEntry.getKey());
            // pushing the char back to heap
            if(previous!=null){
                maxFreqChar.add(previous);
                previous=null;
            }
            
            // setting previous to the most recent used char
            if(count != 0){
                previous = new AbstractMap.SimpleEntry<>(currentEntry.getKey(), count);
            }
        }
        return result.toString();
    }
    public static void main(String args[]) {
        String[] inputs = {
            "programming",
            "hello",
            "fofjjb",
            "abbacdde",
            "aba",
            "awesome",
            "aaab",
            "aab"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput string: \"" + inputs[i] + "\"");
            String output = reorganizeString(inputs[i]);
            output = (output.length() == 0) ? "''" : output;
            System.out.println("\tReorganized string: \"" + output + "\"");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reorganize String

Just the code

Here’s the complete solution to this problem:

import java.util.*;
class Reorganize {
    public static String reorganizeString(String str) {
        Map <Character, Integer> charCounter = new HashMap <> ();
        for (char c: str.toCharArray()) {
            int freq = charCounter.getOrDefault(c, 0) + 1;
            charCounter.put(c, freq);
        }
        PriorityQueue <Map.Entry <Character, Integer>> maxFreqChar = new PriorityQueue <Map.Entry <Character, Integer>> (
            (item1, item2) -> item2.getValue() - item1.getValue());
        maxFreqChar.addAll(charCounter.entrySet());
        Map.Entry <Character, Integer> previous = null;
        StringBuilder result = new StringBuilder(str.length());
        while (!maxFreqChar.isEmpty() || previous!=null) {
            if (previous != null && maxFreqChar.isEmpty())
                return "";
            
            Map.Entry <Character, Integer> currentEntry = maxFreqChar.poll();
            int count=currentEntry.getValue()-1;
            result.append(currentEntry.getKey());
            if(previous!=null){
                maxFreqChar.add(previous);
                previous=null;
            }
            
            if(count != 0){
                previous = new AbstractMap.SimpleEntry<>(currentEntry.getKey(), count);
               
            }
        }
        return result.toString();
    }
    public static void main(String args[]) {
        String[] inputs = {
            "programming",
            "hello",
            "fofjjb",
            "abbacdde",
            "aba",
            "awesome",
            "aaab",
            "aab"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput string: \"" + inputs[i] + "\"");
            String output = reorganizeString(inputs[i]);
            output = (output.length() == 0) ? "''" : output;
            System.out.println("\tReorganized string: \"" + output + "\"");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reorganize String

Solution summary

  1. Store each character and its frequency in a hash map.
  2. Construct a max-heap using the character frequency data so that the most frequently occurring character is at the root of the heap.
  3. Iterate over the heap until all the characters have been considered.
    • Pop the most frequently occurring character from the heap and append it to the result string.
    • Decrement the count of the popped character (since we have used one occurrence of it).
    • Push the popped character back onto the heap in the next iteration if the updated frequency is greater than 00.
  4. After all the iterations, return the reorganized string.
  5. If the heap becomes empty and there is still an element exist to push into the heap, it indicates that reorganization of the string is not possible, return an empty string.

Time complexity

As we iterate through the heap, every popped element may be pushed back onto the heap. This process is repeated until we have considered all the characters in the input string. Therefore, the iteration runs O(n)O(n) times, where nn is the number of characters in the string. The worst-case time complexity of the push operation is O(log⁡(c))O(\log(c)), where cc is the number of distinct characters in the string. Now, the time complexity becomes O(nlog⁡(c)).O(n \log(c)). Since the upper bound on cc is the size of the alphabet, which is 26, the log⁡(c)\log(c) term is effectively a constant. As a result, we may say that the overall time complexity is O(n)O(n).

Space complexity

In our solution, we employed two data structures: a hash map and a heap. The hash map is responsible for storing the frequencies of characters in the input string, while the heap is used in the solution to find the desired string. Both data structures store lowercase alphabets. The maximum capacity of each data structure is 2626 — a fixed number. As a result, the space complexity of our solution is O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.