Reorganize String - Practice Coding Problems

Reorganize String - Problem

Hash Table String Greedy Sorting Heap (Priority Queue) Counting Medium

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" (empty string) if not possible.

Input & Output

Example 1 — Basic Case

$ Input: s = "aab"

› Output: "aba"

💡 Note: We can rearrange "aab" to "aba" where no two adjacent characters are the same. Another valid answer would be "baa".

Example 2 — Impossible Case

$ Input: s = "aaab"

› Output: ""

💡 Note: We have 3 'a's and 1 'b'. Since 'a' appears more than (4+1)/2 = 2.5 times, it's impossible to arrange without adjacent duplicates.

Example 3 — Single Character

$ Input: s = "a"

› Output: "a"

💡 Note: Single character strings are always valid since there are no adjacent pairs to worry about.

Constraints

1 ≤ s.length ≤ 500
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count character frequencies and check feasibility

Strategic Placement

Place characters to avoid adjacent duplicates

Valid Output

Return rearranged string or empty string if impossible

Key Takeaway

🎯 Key Insight: Use frequency counting and strategic placement - if any character appears more than ⌈n/2⌉ times, rearrangement is impossible

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is that if any character appears more than ⌈n/2⌉ times, rearrangement is impossible. The optimal approach uses a max heap to always select the most frequent available character that won't create adjacent duplicates. Time: O(n log k), Space: O(k) where k is the number of unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count with Greedy Placement	O(n log k)	O(k)	Count character frequencies and place characters greedily to avoid adjacency
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible permutations and check if any is valid
Priority Queue (Max Heap) Approach	O(n log k)	O(k)	Use a max heap to always select the most frequent available character

Frequency Count with Greedy Placement — Algorithm Steps

Count frequency of each character
Check if any character appears more than (n+1)/2 times
Place characters alternately starting with most frequent

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how often each character appears

Sort by Frequency

Order characters by frequency (most frequent first)

Alternate Placement

Place at even indices, then odd indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int freq;
} CharFreq;

int compare(const void *a, const void *b) {
    CharFreq *cf1 = (CharFreq*)a;
    CharFreq *cf2 = (CharFreq*)b;
    return cf2->freq - cf1->freq;
}

char* solution(char *s) {
    int len = strlen(s);
    if (len <= 1) {
        char *result = malloc((len + 1) * sizeof(char));
        strcpy(result, s);
        return result;
    }
    
    int counter[26] = {0};
    for (int i = 0; i < len; i++) {
        counter[s[i] - 'a']++;
    }
    
    int maxFreq = 0;
    for (int i = 0; i < 26; i++) {
        if (counter[i] > maxFreq) {
            maxFreq = counter[i];
        }
    }
    
    if (maxFreq > (len + 1) / 2) {
        char *result = malloc(1 * sizeof(char));
        strcpy(result, "");
        return result;
    }
    
    CharFreq chars[26];
    int charCount = 0;
    for (int i = 0; i < 26; i++) {
        if (counter[i] > 0) {
            chars[charCount].ch = 'a' + i;
            chars[charCount].freq = counter[i];
            charCount++;
        }
    }
    
    qsort(chars, charCount, sizeof(CharFreq), compare);
    
    char *result = malloc((len + 1) * sizeof(char));
    result[len] = '\0';
    int idx = 0;
    
    for (int i = 0; i < charCount; i++) {
        for (int j = 0; j < chars[i].freq; j++) {
            result[idx] = chars[i].ch;
            idx += 2;
            if (idx >= len) {
                idx = 1;
            }
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char *result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

O(n) to count frequencies, O(n log k) for sorting where k is number of unique characters

⚡ Linearithmic

Space Complexity

O(k)

Hash map to store character frequencies where k is number of unique characters

✓ Linear Space

156.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count with Greedy Placement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler