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

import java.util.*;

public class Solution {
    private boolean isValid(String s) {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) return false;
        }
        return true;
    }
    
    public String rearrangeStringBrute(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        
        return permute(chars, 0);
    }
    
    private String permute(char[] chars, int start) {
        if (start == chars.length) {
            String s = new String(chars);
            return isValid(s) ? s : null;
        }
        
        for (int i = start; i < chars.length; i++) {
            swap(chars, start, i);
            String result = permute(chars, start + 1);
            if (result != null) return result;
            swap(chars, start, i);
        }
        
        return null;
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

import java.util.*;

public class Solution {
    public String rearrangeString(String s) {
        // Count frequencies
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        
        // Check if valid
        int n = s.length();
        for (int count : freq.values()) {
            if (count > (n + 1) / 2) {
                return "";
            }
        }
        
        // Max-heap based on frequency
        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();
        int[] prev = {0, '#'};
        
        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            result.append((char)curr[1]);
            
            if (prev[0] > 0) {
                maxHeap.offer(prev);
            }
            
            prev = new int[]{curr[0] - 1, curr[1]};
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rearrangeString("aab"));   // Output: "aba"
        System.out.println(sol.rearrangeString("aaab"));  // Output: ""
        System.out.println(sol.rearrangeString("aabb"));  // Output: "abab"
    }
}