why do you even need to use PriorityQueue here.
Because they need to start with the most common character, using heap is better than built-in sort I think. What’s your opinion?
Here I’m using heap to solve this problem:
Can someone explain how to use heap to solve this problem?
What is the time complexity?
res = []
counts = Counter(s)
heap = [(-v, char) for char, v in counts.items()]
heapq.heapify(heap)
while heap:
if len(res) > 0 and heap[0][1] == res[-1]:
v1, c1 = heapq.heappop(heap)
if not heap: return False
v2, c2 = heapq.heappop(heap)
res.append(c2)
v2 += 1
if v2 < 0:
heapq.heappush(heap, (v2, c2))
heapq.heappush(heap, (v1, c1))
else:
v1, c1 = heapq.heappop(heap)
res.append(c1)
v1 += 1
if v1 < 0:
heapq.heappush(heap, (v1, c1))
return res
I understand it but as I described I use my own heap. It gives me the results that tests wanted on LOCAL runs but when I paste the code here it gives unpredictable results or failing.
The reset of pointer to fill out odd after even is filled out is such a neat trick. Helpful solution, thanks.
I am looking for some help better understanding time complexity, I feel like my solution is more efficient than the proposed solution (or at least equivalent) but I just want to make sure I am not missing anything. Please let me know your thoughts on the below solution:
public static String reorganizeString(String s) {
PriorityQueue pq1 = new PriorityQueue<>();
//Add all chars to a heap to ensure that it is sorted
//O(n) operation
for (int i = 0; i < s.length(); i++) {
String c = s.substring(i, i+1);
pq1.add(c);
}
//Add all chars to a list, they will now be in sorted order
//O(n) operation
List<String> l = new ArrayList<>();
while (!pq1.isEmpty()) {
l.add(pq1.poll());
}
//Iterate through the list
//O(n) operation although technically O(n/2) as we grab 2 chars each iteration
String res = "";
while (!l.isEmpty()) {
//Grab two chars each itteration, one from the front and one from the back
String c1 = l.remove(0);
String c2 = l.size() > 0? l.remove(l.size() - 1) : "";
//If the chars are not equal keep building the return string
if (!c1.equals(c2)) {
res += c1;
res += c2;
}
//If we find two chars that are equal it is impossible to arrange chars that are not the same
else {
return "";
}
}
return res;
}
I used BFS to solve the problem:
func reorganizeString(s string) string {
charmap := make(map[byte]int) // char → count
for i := 0; i < len(s); i++ {
charmap[s[i]]++
}
if o := reorganizeStringInternal(“”, len(s), charmap); o == “” {
return “Impossible”
}
return “Valid”
}
func reorganizeStringInternal(out string, outlen int, charmap map[byte]int) string {
if len(out) == outlen {
return out
}
for k, v := range charmap {
if out == “” {
charmap[k]–
if o := reorganizeStringInternal(out + string(k), outlen, charmap); o != “” {
return o
}
charmap[k]++
} else if out[len(out)-1] != k && v > 0 {
charmap[k]–
if o := reorganizeStringInternal(out + string(k), outlen, charmap); o != “” {
return o
}
charmap[k]++
}
}
return “”
}
Each insertion in priority queue costs O(log(n)) so the first part of your solution costs O(n log(n)). But the most important thing is that the result of your algorithm is not guaranteed to be a valid arrangement. For example, for the input “aabbc”, it will return “acabb”.
added to the end of the article
added to the end of the article
Really enjoyed this question. This was very clever -“If there are more of one character than the number of evens, it is impossible to rearrange the string so no adjacent characters are the same.”
I was not quite that clever and I also doubt I’d be that clever under pressure. My approach is a little less efficient but captures the same idea as the provided solution and (in my opinion) is more realistic for what someone can come up with:
- Create the same heap with counts and characters.
- Start creating the result string by popping characters form the heap.
2.1 As you do so, decrement the counts in the dictionary.
2.2 Also check to see if the character being added is equal to the last character that in result. If it is, return empty string. - When the queue is empty, fill it again with the items from the dictionary(char : count) with the now decremented counts. Only push character counts that are greater than zero. (This is the less efficient part. Otherwise, everything else is pretty much the same.)
- Do this entire process until the resulting string is the same length as the input string.
Again I thought the “even” observation is really neat, but I’m not sure how many people can actually come up with that under pressure.
Wouldn’t it be faster to add the counts to a dictionary, and then loop through and add to the string as appropriate? I think this solution is O(2N) => O(N):
def reorganize_string(s: str) -> str:
# Add unique letters and their counts to dictionary
counts = {}
zeros = set()
sol = []
for char in s:
if char not in counts:
counts[char] = 0
counts[char] += 1
# Loop through letters
while len(counts) > 1:
for char in counts:
# Add letter to solution
sol.append(char)
# Decrement count
counts[char] -= 1
if counts[char] == 0:
zeros.add(char) # Mark for deletion
# Pop letters with zero instances left from dictionary
for char in zeros:
counts.pop(char)
zeros = set()
# If more than one of this letter left, the task cannot be completed
for char in counts: # Should only be one entry remaining
if counts[char] > 1: return ''
sol.append(char)
return ''.join(sol)
You’re right, here a heap / PriorityQueue is an overkill since we don’t need to process the remaining characters in order – we just need the most frequent one first, the order of the remaining frequencies can be arbitrary. In other words, no need to sort the counts, it’s sufficient to get their maximum.
Hey there, same here 
There is a mistake in the Main method in C# implementation where it compares if dictionaries are the same, I replaced this:
if (!sCounter.Equals(resCounter)) {
Console.WriteLine(“Not rearrangement”);
return;
}
with this:
foreach(char c in sCounter.Keys)
{
if (!resCounter.ContainsKey(c) || resCounter[c] != sCounter[c])
{
Console.WriteLine(“Not rearrangement”);
return;
}
}
and all works perfectly, FYI @moderators @algo.monster
I think I managed to do this in O(N) time and O(1) auxiliary space (in addition to the return string which is O(N) obviously) using heap 
Oh right, it’s literally the same as solution has. Not sure why k is added to the complexity calculation when it states ‘where k is the number of distinct chars’ - well there is finite number of such depending on ASCII or Unicode so to me it’s O(1) giving O(N+1) time and O(1) space, no?