Prime Number of Set Bits in Binary Representation
Description
Given a string s, rearrange its characters so that no two adjacent characters are the same.
Return any valid rearrangement of s, or return an empty string "" if no valid rearrangement is possible.
A rearrangement becomes impossible when any single character appears so frequently that there is no way to separate all its occurrences with other characters.
Examples
Example 1
Input: s = "aab"
Output: "aba"
Explanation: The string has two 'a's and one 'b'. If we place them as "aab" or "baa", the two 'a's are adjacent. But "aba" works — 'a' at positions 0 and 2 are separated by 'b' at position 1. No two adjacent characters are the same.
Example 2
Input: s = "aaab"
Output: ""
Explanation: The string has three 'a's and one 'b'. No matter how we arrange them — "aaba", "abaa", "baaa", "aab a" — at least two 'a's will always be adjacent. With 3 'a's and only 1 other character, we need at least 2 separators but only have 1. So it's impossible, and we return an empty string.
Example 3
Input: s = "vvvlo"
Output: "vlvov"
Explanation: The character 'v' appears 3 times, 'l' once, and 'o' once. The length is 5, and the maximum allowed frequency is (5+1)/2 = 3. Since 'v' appears exactly 3 times, a valid arrangement exists. One solution is "vlvov" — each 'v' is separated by at least one different character.
Constraints
- 1 ≤ s.length ≤ 500
sconsists of lowercase English letters.
Editorial
Brute Force
Intuition
The most direct approach is to try all possible permutations of the string and check if any of them has no two adjacent characters that are the same.
Imagine you have letter tiles and you want to lay them out in a line. You try every possible ordering, and for each ordering, you check: does any tile match the tile right next to it? If you find an arrangement where no neighbors match, that's your answer.
The feasibility check itself is simple — walk through the string and compare each character with the next one. If any pair matches, that permutation is invalid.
Step-by-Step Explanation
Let's trace through s = "aab":
The characters are ['a', 'a', 'b']. We generate all permutations:
Step 1: Permutation "aab" → check adjacent pairs: (a,a) — MATCH! Invalid.
Step 2: Permutation "aba" → check adjacent pairs: (a,b) OK, (b,a) OK — No matches! Valid!
Step 3: Return "aba".
We got lucky and found it on the second try. But in the worst case, we might need to check all n! permutations.
For s = "aaab":
Step 1-6: Try all permutations: "aaab", "aaba", "abaa", "baaa", "aaba", "abaa"... Every permutation has at least two adjacent 'a's.
Step 7: All permutations exhausted. Return "".
Algorithm
- Generate all permutations of the input string.
- For each permutation:
a. Check every pair of adjacent characters.
b. If no adjacent pair has matching characters, return this permutation. - If no valid permutation found, return "".
Code
class Solution {
public:
string reorganizeString(string s) {
string sorted_s = s;
sort(sorted_s.begin(), sorted_s.end());
do {
bool valid = true;
for (int i = 0; i < (int)sorted_s.size() - 1; i++) {
if (sorted_s[i] == sorted_s[i + 1]) {
valid = false;
break;
}
}
if (valid) return sorted_s;
} while (next_permutation(sorted_s.begin(), sorted_s.end()));
return "";
}
};from itertools import permutations
class Solution:
def reorganizeString(self, s: str) -> str:
for perm in set(permutations(s)):
candidate = ''.join(perm)
valid = True
for i in range(len(candidate) - 1):
if candidate[i] == candidate[i + 1]:
valid = False
break
if valid:
return candidate
return ""class Solution {
private String result = "";
private boolean found = false;
public String reorganizeString(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
boolean[] used = new boolean[chars.length];
backtrack(chars, used, new StringBuilder(), chars.length);
return result;
}
private void backtrack(char[] chars, boolean[] used, StringBuilder sb, int n) {
if (found) return;
if (sb.length() == n) {
// Check validity
boolean valid = true;
for (int i = 0; i < n - 1; i++) {
if (sb.charAt(i) == sb.charAt(i + 1)) {
valid = false;
break;
}
}
if (valid) {
result = sb.toString();
found = true;
}
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) continue;
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;
used[i] = true;
sb.append(chars[i]);
backtrack(chars, used, sb, n);
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}Complexity Analysis
Time Complexity: O(n! × n)
There are up to n! permutations of a string of length n. For each permutation, we scan the string to check adjacency, which takes O(n). Total: O(n! × n). For n = 500, this is astronomically large and completely impractical.
Space Complexity: O(n)
We need O(n) space to store a single permutation at a time.
Why This Approach Is Not Efficient
The brute force generates up to n! permutations. Even for modest inputs like n = 20, this is 2.4 × 10^18 — far beyond any reasonable time limit. For n up to 500, this is completely infeasible.
The fundamental waste is that we generate and validate random orderings without any intelligence. We don't leverage the key insight: the problem is really about character frequencies. If a character appears too often, no arrangement works. If frequencies allow a solution, we can construct one directly without trial and error.
Instead of blindly permuting, we should think about which characters need the most separation and place them strategically. This leads to greedy approaches based on character frequencies.
Better Approach - Max-Heap Greedy
Intuition
Instead of trying all permutations, we can build the result string character by character using a greedy strategy: always place the most frequent character that is different from the last character placed.
Think of it like arranging flowers in a vase. You have piles of different colored flowers, and you don't want two flowers of the same color next to each other. At each position, you pick from the largest pile available — but if the largest pile has the same color as the flower you just placed, you pick from the second-largest pile instead.
A max-heap is perfect for this. It keeps characters sorted by frequency, so we can always quickly get the most frequent available character. After placing a character, we decrease its count and push it back (if count > 0). But we need to make sure we don't pick the same character twice in a row — so after popping the top, if it matches the last placed character, we pop the next one, use it, then push the first one back.
Before starting, we check feasibility: if any character's frequency exceeds ⌈n/2⌉ (i.e., (n + 1) // 2), it's impossible to arrange without adjacency.
Step-by-Step Explanation
Let's trace through s = "aaabbc" (frequencies: a=3, b=2, c=1, n=6):
Feasibility check: max frequency = 3, threshold = (6+1)//2 = 3. Since 3 ≤ 3, a valid arrangement is possible.
Max-heap initially: [(3,'a'), (2,'b'), (1,'c')]
Step 1: Pop (3,'a'). Result = "a". Push back (2,'a'). Heap: [(2,'a'), (2,'b'), (1,'c')].
Step 2: Pop (2,'b') — we can't use 'a' again because it was last placed. Wait, actually 'b' ≠ 'a', so we can use the top. Pop (2,'b'). Result = "ab". Push back (1,'b'). Heap: [(2,'a'), (1,'b'), (1,'c')].
Actually, let me re-trace with the correct algorithm: pop the most frequent, if it matches last char, pop the second most frequent instead.
Step 1: Pop max = (3,'a'). Last char = none. Place 'a'. Result = "a". Push (2,'a') back. Heap: [(2,'a'), (2,'b'), (1,'c')].
Step 2: Pop max = (2,'a'). Last char = 'a'. CONFLICT! Pop second max = (2,'b'). Place 'b'. Result = "ab". Push (2,'a') back (it was popped but not used, push it back). Push (1,'b') back. Heap: [(2,'a'), (1,'b'), (1,'c')].
Step 3: Pop max = (2,'a'). Last char = 'b'. No conflict. Place 'a'. Result = "aba". Push (1,'a') back. Heap: [(1,'a'), (1,'b'), (1,'c')].
Step 4: Pop max = (1,'a'). Last char = 'a'. CONFLICT! Pop second = (1,'b'). Place 'b'. Result = "abab". Push (1,'a') back. Push (0,'b') — don't push zero. Heap: [(1,'a'), (1,'c')].
Step 5: Pop max = (1,'a'). Last char = 'b'. No conflict. Place 'a'. Result = "ababa". Push (0,'a') — don't push zero. Heap: [(1,'c')].
Step 6: Pop max = (1,'c'). Last char = 'a'. No conflict. Place 'c'. Result = "ababac". Heap empty.
Final result: "ababac".
Max-Heap Greedy — Build String by Always Picking Most Frequent Valid Character — Watch how a max-heap keeps characters sorted by frequency. At each step, we pop the most frequent character that differs from the last placed character, ensuring no adjacent duplicates.
Algorithm
- Count the frequency of each character in the string.
- If any character's frequency > (n + 1) / 2, return "" (impossible).
- Build a max-heap with entries (frequency, character).
- Initialize an empty result string.
- While the heap is not empty:
a. Pop the top (most frequent character).
b. If it matches the last character in the result:- Pop the second-most-frequent character instead.
- If no second element exists, return "" (shouldn't happen if feasibility check passed).
- Place the second character, decrease its frequency, push back if > 0.
- Push the first character back into the heap.
c. Otherwise, place the top character, decrease its frequency, push back if > 0.
- Return the result string.
Code
class Solution {
public:
string reorganizeString(string s) {
int n = s.size();
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
// Check feasibility
for (auto& [ch, cnt] : freq) {
if (cnt > (n + 1) / 2) return "";
}
// Max-heap: (frequency, character)
priority_queue<pair<int, char>> maxHeap;
for (auto& [ch, cnt] : freq) {
maxHeap.push({cnt, ch});
}
string result;
while (!maxHeap.empty()) {
auto [cnt1, ch1] = maxHeap.top();
maxHeap.pop();
if (!result.empty() && result.back() == ch1) {
// Conflict: use second most frequent
if (maxHeap.empty()) return "";
auto [cnt2, ch2] = maxHeap.top();
maxHeap.pop();
result += ch2;
if (cnt2 - 1 > 0) maxHeap.push({cnt2 - 1, ch2});
maxHeap.push({cnt1, ch1}); // Push back unused
} else {
result += ch1;
if (cnt1 - 1 > 0) maxHeap.push({cnt1 - 1, ch1});
}
}
return result;
}
};import heapq
from collections import Counter
class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
freq = Counter(s)
# Check feasibility
if max(freq.values()) > (n + 1) // 2:
return ""
# Max-heap (negate freq for max behavior)
max_heap = [(-cnt, ch) for ch, cnt in freq.items()]
heapq.heapify(max_heap)
result = []
while max_heap:
cnt1, ch1 = heapq.heappop(max_heap)
if result and result[-1] == ch1:
# Conflict: use second most frequent
if not max_heap:
return ""
cnt2, ch2 = heapq.heappop(max_heap)
result.append(ch2)
if cnt2 + 1 < 0: # Remember: negated
heapq.heappush(max_heap, (cnt2 + 1, ch2))
heapq.heappush(max_heap, (cnt1, ch1)) # Push back
else:
result.append(ch1)
if cnt1 + 1 < 0:
heapq.heappush(max_heap, (cnt1 + 1, ch1))
return ''.join(result)class Solution {
public String reorganizeString(String s) {
int n = s.length();
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
// Check feasibility
for (int cnt : freq.values()) {
if (cnt > (n + 1) / 2) return "";
}
// Max-heap: (frequency, character)
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] != a[0] ? b[0] - a[0] : a[1] - b[1]
);
for (var entry : freq.entrySet()) {
maxHeap.offer(new int[]{entry.getValue(), entry.getKey()});
}
StringBuilder result = new StringBuilder();
while (!maxHeap.isEmpty()) {
int[] top = maxHeap.poll();
int cnt1 = top[0];
char ch1 = (char) top[1];
if (result.length() > 0 && result.charAt(result.length() - 1) == ch1) {
if (maxHeap.isEmpty()) return "";
int[] second = maxHeap.poll();
int cnt2 = second[0];
char ch2 = (char) second[1];
result.append(ch2);
if (cnt2 - 1 > 0) maxHeap.offer(new int[]{cnt2 - 1, ch2});
maxHeap.offer(new int[]{cnt1, ch1});
} else {
result.append(ch1);
if (cnt1 - 1 > 0) maxHeap.offer(new int[]{cnt1 - 1, ch1});
}
}
return result.toString();
}
}Complexity Analysis
Time Complexity: O(n log k)
Where n is the string length and k is the number of unique characters (at most 26). We process each of the n characters once, and each heap operation (push/pop) takes O(log k). Since k ≤ 26, this is effectively O(n log 26) = O(n). But in general for arbitrary alphabets, it's O(n log k).
Space Complexity: O(k + n)
The frequency map uses O(k) space, the heap holds at most k entries, and the result string is O(n). Since k ≤ 26, the dominant term is O(n).
Why This Approach Is Not Efficient
The max-heap approach works correctly and runs in O(n log k) time, which is efficient. However, it involves a constant overhead of heap operations (push and pop) at every character placement. Since k ≤ 26, the log factor is small, but we still do two heap operations per character.
More importantly, the heap approach is conceptually more complex than necessary. There's a simpler approach that doesn't need a heap at all: sort by frequency and place characters at alternating indices. This achieves the same goal with a single pass through the sorted characters and direct array placement — no per-character heap operations needed.
The key insight is that if we place the most frequent characters first at even indices (0, 2, 4, ...), then fill odd indices (1, 3, 5, ...) with the remaining characters, we guarantee no adjacent duplicates. This avoids the overhead of maintaining a dynamic priority structure.
Optimal Approach - Sort by Frequency + Alternating Placement
Intuition
The cleanest solution exploits a powerful observation: if we place characters at every other position, no two copies of the same character can be adjacent.
Picture a row of empty seats numbered 0 through n-1. First, fill seats 0, 2, 4, 6... (the even positions). Then fill seats 1, 3, 5, 7... (the odd positions). If we place all copies of one character before moving to the next, and we start with the most frequent character, each character's copies will land in non-adjacent positions.
Why does this work? Characters placed at even positions are separated by at least one gap. When we switch from even to odd positions, the last even position and the first odd position (index 1) are not adjacent to each other in terms of placement — the character at index 0 (even) is adjacent to index 1 (odd), but they'll be different characters because we exhausted the even slots first with the most frequent character.
The algorithm is:
- Count character frequencies.
- Check if the max frequency exceeds ⌈n/2⌉ — if so, return "".
- Sort characters by frequency (descending).
- Place them into the result at positions 0, 2, 4, ..., then 1, 3, 5, ...
Step-by-Step Explanation
Let's trace through s = "aaabbc" (n=6):
Step 1: Count frequencies: a=3, b=2, c=1.
Step 2: Check feasibility: max_freq = 3, threshold = (6+1)//2 = 3. Since 3 ≤ 3, it's valid.
Step 3: Sort by frequency descending: [('a',3), ('b',2), ('c',1)].
Step 4: Create result array of size 6: [_, _, _, _, _, _]. Start index i = 0.
Step 5: Place 'a' (3 copies):
- Position 0: result = [a, _, _, _, _, _], i = 2
- Position 2: result = [a, _, a, _, _, _], i = 4
- Position 4: result = [a, _, a, _, a, _], i = 6
- i = 6 ≥ 6, switch to odd: i = 1
Step 6: Place 'b' (2 copies):
- Position 1: result = [a, b, a, _, a, _], i = 3
- Position 3: result = [a, b, a, b, a, _], i = 5
Step 7: Place 'c' (1 copy):
- Position 5: result = [a, b, a, b, a, c], i = 7
Step 8: Join array → "ababac". Verify: a≠b, b≠a, a≠b, b≠a, a≠c. All adjacent pairs differ!
Alternating Placement — Fill Even Indices First, Then Odd — Watch how sorting characters by frequency and placing them at alternating positions ensures no two identical characters end up adjacent.
Algorithm
- Count the frequency of each character.
- Find the maximum frequency. If it exceeds (n + 1) / 2, return "".
- Sort characters by frequency in descending order.
- Create a result array of size n.
- Set placement index i = 0.
- For each character (in sorted frequency order), for each copy of that character:
a. Place the character at position i in the result array.
b. Increment i by 2.
c. If i ≥ n, reset i to 1 (switch from even to odd positions). - Join the result array into a string and return it.
Code
class Solution {
public:
string reorganizeString(string s) {
int n = s.size();
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
// Check feasibility
int maxFreq = 0;
for (auto& [ch, cnt] : freq) {
maxFreq = max(maxFreq, cnt);
}
if (maxFreq > (n + 1) / 2) return "";
// Sort characters by frequency (descending)
vector<pair<int, char>> charList;
for (auto& [ch, cnt] : freq) {
charList.push_back({cnt, ch});
}
sort(charList.rbegin(), charList.rend());
// Place at alternating indices
string result(n, ' ');
int idx = 0;
for (auto& [cnt, ch] : charList) {
for (int k = 0; k < cnt; k++) {
result[idx] = ch;
idx += 2;
if (idx >= n) idx = 1;
}
}
return result;
}
};from collections import Counter
class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
freq = Counter(s)
# Check feasibility
max_freq = max(freq.values())
if max_freq > (n + 1) // 2:
return ""
# Place characters at alternating indices
result = [''] * n
idx = 0
# Process characters in descending frequency order
for char, count in freq.most_common():
for _ in range(count):
result[idx] = char
idx += 2
if idx >= n:
idx = 1
return ''.join(result)class Solution {
public String reorganizeString(String s) {
int n = s.length();
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
// Check feasibility
int maxFreq = 0;
for (int f : freq) maxFreq = Math.max(maxFreq, f);
if (maxFreq > (n + 1) / 2) return "";
// Sort characters by frequency (descending)
Integer[] indices = new Integer[26];
for (int i = 0; i < 26; i++) indices[i] = i;
Arrays.sort(indices, (a, b) -> freq[b] - freq[a]);
// Place at alternating indices
char[] result = new char[n];
int idx = 0;
for (int ci : indices) {
if (freq[ci] == 0) break;
for (int k = 0; k < freq[ci]; k++) {
result[idx] = (char) ('a' + ci);
idx += 2;
if (idx >= n) idx = 1;
}
}
return new String(result);
}
}Complexity Analysis
Time Complexity: O(n + k log k)
Counting character frequencies takes O(n). Sorting the k unique characters by frequency takes O(k log k). Since k ≤ 26 for lowercase English letters, this is O(26 log 26) = O(1). Placing all n characters into the result array takes O(n). Overall: O(n).
For a general alphabet of size k, the complexity would be O(n + k log k).
Space Complexity: O(n + k)
The frequency map uses O(k) space. The result array uses O(n) space. Since k ≤ 26, the dominant term is O(n).