DSA 450 Notes

Problem Statement

Given a string with repeated characters, rearrange the characters such that no two adjacent characters are the same. If not possible, return an empty string.

Example:

Input: "aab"
Output: "aba"

Example 2:

Input: "aaab"
Output: "" (not possible)
Explanation: 'a' appears 3 times but string length is 4. Cannot avoid adjacent 'a's.

Approach 1: Brute Force (Generate All Permutations)

Intuition

Generate all permutations of the string and check if any satisfies the no-adjacent-same constraint.

Algorithm

Generate all permutations of the string
For each permutation, check if any two adjacent characters are same
Return the first valid permutation found

java

import java.util.*;

public class Solution {
    private boolean isValid(char[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) return false;
        }
        return true;
    }
    
    public String reorganizeString(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        
        // Generate permutations (simplified version)
        // In practice, this is too slow
        return generatePermutations(arr);
    }
    
    // This would need a proper permutation generator
    private String generatePermutations(char[] arr) {
        // Placeholder - actual implementation would be complex
        return "";
    }
}

Complexity Analysis

Time Complexity: O(n! * n) - n! permutations, O(n) to check each
Space Complexity: O(n) - For recursion/iteration

Approach 2: Greedy with Max Heap (Optimal)

Intuition

Always place the most frequent character that's different from the last placed character. Use a max heap to efficiently get the most frequent character.

Algorithm

Count frequency of each character
Check if any character appears more than (n+1)/2 times (impossible case)
Use max heap to always get the most frequent character
Alternate between most frequent characters

java

import java.util.*;

public class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        
        // Count frequencies
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            if (freq.get(c) > (n + 1) / 2) {
                return "";
            }
        }
        
        // Max heap: (frequency, character)
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        
        for (Map.Entry<Character, Integer> e : freq.entrySet()) {
            maxHeap.offer(new int[]{e.getValue(), e.getKey()});
        }
        
        StringBuilder result = new StringBuilder();
        
        while (maxHeap.size() >= 2) {
            int[] first = maxHeap.poll();
            int[] second = maxHeap.poll();
            
            result.append((char) first[1]);
            result.append((char) second[1]);
            
            if (first[0] > 1) {
                maxHeap.offer(new int[]{first[0] - 1, first[1]});
            }
            if (second[0] > 1) {
                maxHeap.offer(new int[]{second[0] - 1, second[1]});
            }
        }
        
        if (!maxHeap.isEmpty()) {
            result.append((char) maxHeap.poll()[1]);
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n log k) where k is number of unique characters (at most 26)
Space Complexity: O(k) for the heap

Approach 3: Fill Even-Odd Positions

Intuition

Place the most frequent character at even indices (0, 2, 4, ...), then fill remaining characters at remaining positions.

Algorithm

Count frequencies
Find most frequent character
Place it at even indices first
Fill remaining characters at remaining positions

java

public class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] freq = new int[26];
        
        int maxFreq = 0, maxChar = 0;
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
            if (freq[c - 'a'] > maxFreq) {
                maxFreq = freq[c - 'a'];
                maxChar = c - 'a';
            }
        }
        
        if (maxFreq > (n + 1) / 2) {
            return "";
        }
        
        char[] result = new char[n];
        int idx = 0;
        
        // Place most frequent at even indices
        while (freq[maxChar] > 0) {
            result[idx] = (char) ('a' + maxChar);
            freq[maxChar]--;
            idx += 2;
        }
        
        // Place remaining characters
        for (int i = 0; i < 26; i++) {
            while (freq[i] > 0) {
                if (idx >= n) {
                    idx = 1;
                }
                result[idx] = (char) ('a' + i);
                freq[i]--;
                idx += 2;
            }
        }
        
        return new String(result);
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through string
Space Complexity: O(n) - For result string

Why (n+1)/2 Check?

If a character appears more than (n+1)/2 times, it's impossible to place them without adjacency.

Example: n=5

Max frequency allowed = (5+1)/2 = 3
Pattern: a_a_a - character 'a' at positions 0, 2, 4 (3 positions)
If 'a' appears 4 times: aaaa_ - cannot avoid aa

Key Takeaways

Greedy approach works: always use the most frequent unused character
Impossibility check: maxFreq > (n+1)/2 means no solution exists
Max heap efficiently provides the next character to use
Even-odd filling is an elegant O(n) alternative
This is LeetCode 767 and a common interview question
Related: Task Scheduler (with cooling period)

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

Problem Statement

Approach 1: Brute Force (Generate All Permutations)

Intuition

Algorithm

Complexity Analysis

Approach 2: Greedy with Max Heap (Optimal)

Intuition

Algorithm

Complexity Analysis

Approach 3: Fill Even-Odd Positions

Intuition

Algorithm

Complexity Analysis

Why (n+1)/2 Check?

Key Takeaways