Rearrange characters in a String such that no two adjacent characters are same

Last Updated : 17 Feb, 2025

Given a string s with lowercase repeated characters, the task is to rearrange characters in a string so that no two adjacent characters are the same. If it is not possible to do so, then print empty string ("").

Note: Multiple valid rearranged strings can be possible for same input string.

Examples: 

Input: s = "aaabc" 
Output: abaca 
Explanation: No two adjacent characters are same in the output string.

Input: s = "aa"
Output: ""
Explanation: Not Possible

Input: s = "aaaabc" 
Output: ""
Explanation: Not Possible

Try it on GfG Practice
redirect icon

Table of Content

[Approach 1] Using Max Heap - O(n*log n) Time and O(n) Space

The idea is to place the highest frequency character first. We use a priority queue (max heap) and put all characters and ordered by their frequencies (highest frequency character at root). One by one take the highest frequency character from the heap and add it to result. After adding it, just decrease the frequency of the character and then temporarily move this character out of priority queue so that it is not picked again next time.

C++ 
// C++ program to rearrange characters in a string
// so that no two adjacent characters are same.

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

// Function to rearrange character of a string
// so that no two adjacent characters are same
string rearrangeString(string &s) {
    int n = s.length();

    // Store frequencies of all characters in string
    unordered_map<char, int> freq;
    for (int i = 0; i < n; i++)
        freq[s[i]]++;

    // Insert all characters with their frequencies
    // into a priority_queue
    priority_queue<pair<int, char>> pq;
    for (char c = 'a'; c <= 'z'; c++) {
        if (freq[c] > 0) {
            pq.push({ freq[c], c });
        }
    }

    string res = "";

    // work as the previous visited element
    // initial previous element be '#' and it's frequency '-1' 
    pair<int, char> prev = { -1, '#' };

    while (!pq.empty()) {
        
        // pop top element from queue and add it
        // to string.
        pair<int, char> p = pq.top();
        pq.pop();
        
        res.push_back(p.second);

        // IF frequency of previous character is less
        // than zero that means it is useless, we
        // need not to push it
        if (prev.first > 0)
            pq.push(prev);

        // Make current character as the previous 'char'
        // decrease frequency by 'one'
        p.first--;
        prev = p;
    }

    // If length of the resultant string and original
    // string is not same then string is not valid
    if (res.size() != n)
        return "";
    
    // Valid String
    return res;
}

int main() {
    string s = "aaabc";
    cout << rearrangeString(s);
    return 0;
}
Java 
// Java program to rearrange characters in a string
// so that no two adjacent characters are same.

import java.util.*;

class GfG {
    
    // Function to rearrange character of a string
    // so that no two adjacent characters are same
    static String rearrangeString(String s) {
        int n = s.length();
        
        // Store frequencies of all characters in string
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray())
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        
        // Insert all characters with their frequencies
        // into a priority_queue
        PriorityQueue<Map.Entry<Character, Integer>> pq = 
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(freq.entrySet());
        
        StringBuilder res = new StringBuilder();
        
        // Work as the previous visited element
        // Initial previous element be '#' and its frequency '-1'
        Map.Entry<Character, Integer> prev = new AbstractMap.SimpleEntry<>('#', -1);
        
        while (!pq.isEmpty()) {
            // Pop top element from queue and add it
            // to string.
            Map.Entry<Character, Integer> p = pq.poll();
            res.append(p.getKey());
            
            // If frequency of previous character is less
            // than zero that means it is useless, we
            // need not to push it
            if (prev.getValue() > 0)
                pq.offer(prev);
            
            // Make current character as the previous 'char'
            // decrease frequency by 'one'
            prev = new AbstractMap.SimpleEntry<>(p.getKey(), p.getValue() - 1);
        }
        
        // If length of the resultant string and original
        // string is not same then string is not valid
        if (res.length() != n)
            return "";
        
        // Valid String
        return res.toString();
    }
    
    public static void main(String[] args) {
        String s = "aaabc";
        System.out.println(rearrangeString(s));
    }
}
Python 
# Python program to rearrange characters in a string
# so that no two adjacent characters are same.

from collections import Counter
import heapq

def rearrangeString(s):
    n = len(s)
    
    # Store frequencies of all characters in string
    freq = Counter(s)
    
    # Insert all characters with their frequencies
    # into a max heap
    pq = [(-value, key) for key, value in freq.items()]
    heapq.heapify(pq)
    
    res = []
    prev = (0, '')  # previous character and its remaining count
    
    while pq:
        # Pop top element from queue and add it
        # to string.
        count, char = heapq.heappop(pq)
        res.append(char)
        
        # If frequency of previous character is less
        # than zero that means it is useless, we
        # need not to push it
        if prev[0] < 0:
            heapq.heappush(pq, prev)
        
        # Make current character as the previous 'char'
        # decrease frequency by 'one'
        prev = (count + 1, char)
    
    # If length of the resultant string and original
    # string is not same then string is not valid
    if len(res) != n:
        return ""
    
    # Valid String
    return "".join(res)
    
if __name__ == "__main__":
    s = "aaabc"
    print(rearrangeString(s))
C# 
// C# program to rearrange characters in a string
// so that no two adjacent characters are the same.

using System;
using System.Collections.Generic;

class CharFreq {
    public int Frequency;
    public char Character;

    public CharFreq(int frequency, char character) {
        Frequency = frequency;
        Character = character;
    }
}

class CharFreqComparer : IComparer<CharFreq> {
    public int Compare(CharFreq a, CharFreq b) {
        // Sort by frequency in descending order, if equal then by character in ascending order
        int freqCompare = b.Frequency.CompareTo(a.Frequency);
        return freqCompare != 0 ? freqCompare : a.Character.CompareTo(b.Character);
    }
}

class GfG {
    
    // Function to rearrange characters of a string
    // so that no two adjacent characters are the same
    static string rearrangeString(string s) {
        int n = s.Length;

        // Store frequencies of all characters in string
        Dictionary<char, int> freq = new Dictionary<char, int>();
        foreach (char c in s) {
            if (!freq.ContainsKey(c))
                freq[c] = 0;
            freq[c]++;
        }

        // Insert all characters with their frequencies into a sorted set
        SortedSet<CharFreq> pq = new SortedSet<CharFreq>(new CharFreqComparer());
        foreach (var kvp in freq)
            pq.Add(new CharFreq(kvp.Value, kvp.Key));

        List<char> res = new List<char>();
        CharFreq prev = new CharFreq(-1, '#'); // Previous character

        while (pq.Count > 0) {
            // Pop the highest frequency element
            CharFreq p = pq.Min;
            pq.Remove(p);
            res.Add(p.Character);

            // If the previous character still has a remaining count, reinsert it
            if (prev.Frequency > 0)
                pq.Add(prev);

            // Update previous character with a decremented frequency
            p.Frequency--;
            prev = p;
        }

        // If length of the resultant string and original string is not the same, return ""
        if (res.Count != n)
            return "";

        // Valid String
        return new string(res.ToArray());
    }

    static void Main() {
        string s = "aaabc";
        Console.WriteLine(rearrangeString(s));
    }
}
JavaScript 
//Driver Code Starts
// JavaScript program to rearrange characters in a string
// so that no two adjacent characters are the same.

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    insert(count, char) {
        this.heap.push([count, char]);
        this.heapifyUp();
    }

    extractMax() {
        if (this.isEmpty()) return null;
        const max = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.heapifyDown();
        }
        return max;
    }

    heapifyUp() {
        let index = this.size() - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex][0] >= this.heap[index][0]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    heapifyDown() {
        let index = 0;
        while (2 * index + 1 < this.size()) {
            let leftChild = 2 * index + 1;
            let rightChild = 2 * index + 2;
            let largest = leftChild;
            if (rightChild < this.size() && this.heap[rightChild][0] > this.heap[leftChild][0]) {
                largest = rightChild;
            }
            if (this.heap[index][0] >= this.heap[largest][0]) break;
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            index = largest;
        }
    }
}
//Driver Code Ends

// Function to rearrange characters in a string
// so that no two adjacent characters are the same
function rearrangeString(s) {
    let n = s.length;

    // Store frequencies of all characters in string
    let freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }

    // Insert all characters with their frequencies into a max heap
    let pq = new MaxHeap();
    for (let [char, count] of Object.entries(freq)) {
        pq.insert(count, char);
    }

    let res = [];
    let prev = [0, ''];

    while (!pq.isEmpty()) {
        // Extract the character with the highest frequency
        let [count, char] = pq.extractMax();
        res.push(char);

        // If the previous character still has a remaining count, reinsert it
        if (prev[0] > 0) {
            pq.insert(prev[0], prev[1]);
        }

        // Update previous character with decremented frequency
        prev = [count - 1, char];
    }

    // If length of the resultant string and original string is not the same, return ""
    return res.length === n ? res.join('') : "";
}

// Driver Code
const s = "aaabc";
console.log(rearrangeString(s));

Output
acaba

[Approach 2] Using Greedy - O(n) Time and O(n) Space

The idea is to fill all the even positions of the result string first, with the highest frequency character. If there are still some even positions remaining, fill them first. Once even positions are done, then fill the odd positions. This way, it can be ensured that no two adjacent characters are the same. 

Follow the given steps to solve the problem:

  • Calculate the frequencies of every character in the input string.
  • If a character with a maximum frequency has a frequency greater than (n + 1) / 2, then return an empty string, as it is not possible to construct the required string.
  • Now fill the even index positions with the maximum frequency character, if some even positions are remaining then first fill them with remaining characters.
  • Then fill odd index positions with the remaining characters.
  • Return the constructed string.
C++ 
// C++ program to rearrange characters in a string
// so that no two adjacent characters are same.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Function to rearrange character of a string
// so that no two adjacent characters are same
string rearrangeString(string &s) {
    int n = s.length();
    int mxCnt = 0;
    char ch = '#';

    // Store frequencies of all characters in string
    unordered_map<char, int> freq;
    for (int i = 0; i < n; i++) {
        freq[s[i]]++;
        
        if (freq[s[i]] > mxCnt) {
            mxCnt = freq[s[i]];
            ch = s[i];
        }
    }
    
    // Check if the result is possible or not
    if (mxCnt > ((n+1)/2))
        return "";
    
    // Filling the most frequently occurring char at
    // even indices
    int ind = 0;
    while (mxCnt > 0) {
        s[ind] = ch;
        ind = ind + 2;
        mxCnt--;
    }
    freq[ch] = 0;

    // Filling rest of the characters first at even positions, 
    // then odd positions.
    for (char ch = 'a'; ch <= 'z'; ch++) {

        while (freq[ch] > 0) {
            
            // Switch to odd, when all even positions were filled
            ind = (ind >= n) ? 1 : ind;
            s[ind] = ch;
            ind += 2;
            freq[ch]--;
        }
    }
    
    return s;
}

int main() {
    string s = "aaabc";
    cout << rearrangeString(s);
    return 0;
}
Java 
// Java program to rearrange characters in a string
// so that no two adjacent characters are same.
import java.util.*;

class GfG {
    
    // Function to rearrange character of a string
    // so that no two adjacent characters are same
    static String rearrangeString(String s) {
        int n = s.length();
        int mxCnt = 0;
        char ch = '#';

        // Store frequencies of all characters in string
        HashMap<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i++) {
            freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i), 0) + 1);

            if (freq.get(s.charAt(i)) > mxCnt) {
                mxCnt = freq.get(s.charAt(i));
                ch = s.charAt(i);
            }
        }

        // Check if the result is possible or not
        if (mxCnt > ((n + 1) / 2))
            return "";

        // Filling the most frequently occurring char at
        // even indices
        int ind = 0;
        char[] res = s.toCharArray();
        while (mxCnt > 0) {
            res[ind] = ch;
            ind = ind + 2;
            mxCnt--;
        }
        freq.put(ch, 0);

        // Filling rest of the characters first at even positions,
        // then odd positions.
        for (char c = 'a'; c <= 'z'; c++) {
            while (freq.getOrDefault(c, 0) > 0) {
                // Switch to odd, when all even positions were filled
                ind = (ind >= n) ? 1 : ind;
                res[ind] = c;
                ind += 2;
                freq.put(c, freq.get(c) - 1);
            }
        }

        return new String(res);
    }

    public static void main(String[] args) {
        String s = "aaabc";
        System.out.println(rearrangeString(s));
    }
}
Python 
# Python program to rearrange characters in a string
# so that no two adjacent characters are same.

# Function to rearrange character of a string
# so that no two adjacent characters are same
def rearrangeString(s):
    n = len(s)
    mxCnt = 0
    ch = '#'

    # Store frequencies of all characters in string
    freq = {}
    for i in range(n):
        freq[s[i]] = freq.get(s[i], 0) + 1
        
        if freq[s[i]] > mxCnt:
            mxCnt = freq[s[i]]
            ch = s[i]

    # Check if the result is possible or not
    if mxCnt > ((n + 1) // 2):
        return ""
    
    # Filling the most frequently occurring char at
    # even indices
    ind = 0
    s = list(s)
    while mxCnt > 0:
        s[ind] = ch
        ind = ind + 2
        mxCnt -= 1
    freq[ch] = 0

    # Filling rest of the characters first at even positions,
    # then odd positions.
    for ch in 'abcdefghijklmnopqrstuvwxyz':
        while freq.get(ch, 0) > 0:
            
            # Switch to odd, when all even positions were filled
            ind = 1 if ind >= n else ind
            s[ind] = ch
            ind += 2
            freq[ch] -= 1

    return ''.join(s)
    
if __name__ == "__main__":
    s = "aaabc"
    print(rearrangeString(s))
C# 
// C# program to rearrange characters in a string
// so that no two adjacent characters are same.

using System;
using System.Collections.Generic;

class GfG {
    
    // Function to rearrange character of a string
    // so that no two adjacent characters are same
    static string rearrangeString(string s) {
        int n = s.Length;
        int mxCnt = 0;
        char ch = '#';

        // Store frequencies of all characters in string
        Dictionary<char, int> freq = new Dictionary<char, int>();
        foreach (char c in s) {
            if (freq.ContainsKey(c)) {
                freq[c]++;
            } else {
                freq[c] = 1;
            }

            if (freq[c] > mxCnt) {
                mxCnt = freq[c];
                ch = c;
            }
        }

        // Check if the result is possible or not
        if (mxCnt > ((n + 1) / 2))
            return "";

        // Filling the most frequently occurring char at
        // even indices
        int ind = 0;
        char[] res = s.ToCharArray();
        while (mxCnt > 0) {
            res[ind] = ch;
            ind += 2;
            mxCnt--;
        }
        freq[ch] = 0;

        // Filling rest of the characters first at even positions,
        // then odd positions.
        for (char c = 'a'; c <= 'z'; c++) {
            while (freq.ContainsKey(c) && freq[c] > 0) {
                // Switch to odd, when all even positions were filled
                ind = (ind >= n) ? 1 : ind;
                res[ind] = c;
                ind += 2;
                freq[c]--;
            }
        }

        return new string(res);
    }

    static void Main() {
        string s = "aaabc";
        Console.WriteLine(rearrangeString(s));
    }
}
JavaScript 
// JavaScript program to rearrange characters in a string
// so that no two adjacent characters are same.

// Function to rearrange character of a string
// so that no two adjacent characters are same
function rearrangeString(s) {
    const n = s.length;
    let mxCnt = 0;
    let ch = '#';

    // Store frequencies of all characters in string
    let freq = {};
    for (let i = 0; i < n; i++) {
        if (freq[s[i]] === undefined) 
            freq[s[i]] = 0;
            
        freq[s[i]] = freq[s[i]] + 1;
        if (freq[s[i]] > mxCnt) {
            mxCnt = freq[s[i]];
            ch = s[i];
        }
    }

    // Check if the result is possible or not
    if (mxCnt > Math.ceil(n / 2)) return "";

    // Filling the most frequently occurring char at
    // even indices
    let ind = 0;
    let res = new Array(n);
    while (mxCnt > 0) {
        res[ind] = ch;
        ind += 2;
        mxCnt--;
    }
    freq[ch] = 0;
    
    // Filling rest of the characters first at even positions,
    // then odd positions using for loop for (a-z):
    for (let i = 97; i <= 122; i++) {
        let c = String.fromCharCode(i);
        
        // Skip if the character isn't in the string
        if (freq[c] === undefined) continue; 
        
        let cnt = freq[c];
        while (cnt > 0) {
            
            // Switch to odd, when all even positions were filled
            ind = (ind >= n) ? 1 : ind;
            res[ind] = c;
            ind += 2;
            cnt--;
        }
    }
    
    return res.join('');
}

// Driver Code
let s = "aaabc";
console.log(rearrangeString(s));

Output
abaca


 

Comment
Article Tags:
Strings
Greedy
Heap
DSA
+2 More

Explore