Given a string S with repeated characters. The task is to rearrange characters in a string such that no two adjacent characters are the same.
Note: The string has only lowercase English alphabets and it can have multiple solutions. Return any one of them.
Example 1:
Input : str = "geeksforgeeks"
Output: 1
Explanation: All the repeated characters of the
given string can be rearranged so that no 
adjacent characters in the string is equal.
Any correct rearrangement will show a output
of 1.
Example 2:
Input : str = "bbbbb"
Output: 0
Explanation: Repeated characters in the string
cannot be rearranged such that there should not
be any adjacent repeated character.
Your task :
You don't have to read input or print anything. Your task is to complete the functionrearrangeString() which takes the string as input and returns the modified string. If the string cannot be modified return "-1".
Note:The generatedoutput is 1 if the string is successfully rearranged and is 0 if rearranging is not possible.
 
Expected Time Complexity : O(NlogN), N = length of String
Expected Auxiliary Space : O(number of english alphabets)
 
Constraints :
1 <= length of string <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution :

    def rearrangeString(self, str):

        #code here

Solutions:
from collections import *
import heapq

class Solution:

	def rearrangeString(self, str):
		dic = Counter(str)
		heap = [[-count, char] for (char, count) in dic.items()]
		heapq.heapify(heap)
		output = ''
		prev = None
		while heap or prev:
			if prev and (not heap):
				return ''
			(count, char) = heapq.heappop(heap)
			count += 1
			output += char
			if prev:
				heapq.heappush(heap, prev)
				prev = None
			if count != 0:
				prev = [count, char]
		return output


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, s):
		freq = Counter(s)
		pq = [[-count, char] for (char, count) in freq.items()]
		heapq.heapify(pq)
		result = ''
		prev = None
		while pq or prev:
			if prev and (not pq):
				return ''
			(count, char) = heapq.heappop(pq)
			count += 1
			result += char
			if prev:
				heapq.heappush(pq, prev)
				prev = None
			if count != 0:
				prev = [count, char]
		return result


from collections import defaultdict

class Solution:

	def rearrangeString(self, s):
		countDict = {}
		n = len(s)
		for i in s:
			if i in countDict:
				countDict[i] += 1
			else:
				countDict[i] = 1
		c = self.getMaxCountChar(countDict)
		maxCount = countDict[c]
		if maxCount > (n + 1) / 2:
			return ''
		res = [''] * n
		idx = 0
		while maxCount:
			res[idx] = c
			idx += 2
			maxCount -= 1
		del countDict[c]
		for i in countDict:
			while countDict[i] > 0:
				if idx >= n:
					idx = 1
				res[idx] = i
				idx += 2
				countDict[i] -= 1
		return ''.join(res)

	def getMaxCountChar(self, countDict):
		max = 0
		ch = ''
		for (key, value) in countDict.items():
			if value > max:
				max = value
				ch = key
		return ch


from collections import defaultdict

class Solution:

	def rearrangeString(self, s):
		countArray = [0] * 26
		n = len(s)
		for i in s:
			countArray[ord(i) - ord('a')] += 1
		c = self.getMaxCountChar(countArray)
		maxCount = countArray[ord(c) - ord('a')]
		if maxCount > (n + 1) / 2:
			return ''
		res = [''] * n
		idx = 0
		while maxCount:
			res[idx] = c
			idx += 2
			maxCount -= 1
		countArray[ord(c) - ord('a')] = 0
		for i in range(26):
			while countArray[i] > 0:
				if idx >= n:
					idx = 1
				res[idx] = chr(ord('a') + i)
				idx += 2
				countArray[i] -= 1
		return ''.join(res)

	def getMaxCountChar(self, countArray):
		max = 0
		ch = ''
		for i in range(26):
			if countArray[i] > max:
				max = countArray[i]
				ch = chr(i + ord('a'))
		return ch


import heapq as h

class Solution:

	def rearrangeString(self, str):
		hashmap = {}
		maxheap = []
		result = [''] * len(str)
		curr_count = 0
		curr_alphabet = ''
		index = 0
		for i in range(0, len(str)):
			if str[i] in hashmap:
				hashmap[str[i]] = hashmap[str[i]] + 1
			else:
				hashmap[str[i]] = 1
		for (key, value) in hashmap.items():
			h.heappush(maxheap, [-value, key])
		if -maxheap[0][0] > (len(str) + 1) // 2:
			return '-1'
		else:
			index = 0
			while maxheap:
				(curr_count, curr_alphabet) = h.heappop(maxheap)
				curr_count = -1 * curr_count
				for i in range(curr_count):
					result[index] = curr_alphabet
					index += 2
					if index >= len(str):
						index = 1
		return result


import heapq
from collections import Counter

class Solution:

	def rearrangeString(self, str):
		hmap = Counter(str)
		res = []
		for (k, v) in hmap.items():
			res.append([-v, k])
		heapq.heapify(res)
		ans = ''
		while len(res) > 1:
			pop1 = heapq.heappop(res)
			ans += pop1[1]
			pop2 = heapq.heappop(res)
			ans += pop2[1]
			if -1 * pop1[0] > 1:
				heapq.heappush(res, [-1 * (-1 * pop1[0] - 1), pop1[1]])
			if -1 * pop2[0] > 1:
				heapq.heappush(res, [-1 * (-1 * pop2[0] - 1), pop2[1]])
		if res:
			pop = heapq.heappop(res)
			if -1 * pop[0] > 1:
				return '-1'
			else:
				ans += pop[1]
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def rearrangeString(self, s):
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		a = []
		for i in dic.keys():
			heappush(a, [-dic[i], i])
		x = ''
		while a and len(a) != 1:
			(a1, b1) = heappop(a)
			(a2, b2) = heappop(a)
			x = x + b1 + b2
			a1 += 1
			if a1 != 0:
				heappush(a, [a1, b1])
			a2 += 1
			if a2 != 0:
				heappush(a, [a2, b2])
		if len(a) == 1:
			(a1, b1) = heappop(a)
			c = b1 * -a1
			x = x + c
		return x


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, str):
		ans = ''
		temp = []
		rec = Counter(str)
		for (k, f) in rec.items():
			heapq.heappush(temp, (-f, k))
		prev = [1, '']
		while temp:
			(f, k) = heapq.heappop(temp)
			ans += k
			if -prev[0] > 0:
				heapq.heappush(temp, (prev[0], prev[1]))
			f += 1
			prev = [f, k]
		if len(ans) == len(str):
			return ans
		else:
			return '-1'


class Solution:

	def rearrangeString(self, str):
		d = {}
		n = len(str)
		for i in str:
			if i in d:
				d[i] = d[i] + 1
			else:
				d[i] = 1
		arr = []
		for (i, j) in d.items():
			arr.append([i, j])
		arr.sort(key=lambda x: x[1], reverse=True)
		i = 0
		str = [None] * n
		j = 0
		while i < n:
			while i < n and arr[j][1] > 0:
				str[i] = arr[j][0]
				arr[j][1] = arr[j][1] - 1
				i = i + 2
			if arr[j][1] == 0:
				j = j + 1
		i = 1
		while i < n:
			while i < n and arr[j][1] > 0:
				str[i] = arr[j][0]
				arr[j][1] = arr[j][1] - 1
				i = i + 2
			if arr[j][1] == 0:
				j = j + 1
		str = ''.join(str)
		return str


import heapq
from collections import Counter

class Solution:

	def rearrangeString(self, str):
		res = ''
		z = []
		c = Counter(str)
		for (i, j) in c.items():
			heapq.heappush(z, (-j, i))
		p = [1, '']
		while z:
			(i, j) = heapq.heappop(z)
			res += j
			if -p[0] > 0:
				heapq.heappush(z, (p[0], p[1]))
			i += 1
			p = [i, j]
		if len(res) == len(str):
			return res
		else:
			return '-1'


import heapq

class Solution:

	def rearrangeString(self, str):
		d1 = {}
		for i in str:
			if i not in d1:
				d1[i] = 1
			else:
				d1[i] += 1
		max_heap = []
		for (char, freq) in d1.items():
			heapq.heappush(max_heap, (-freq, char))
		s1 = ''
		while len(max_heap) >= 2:
			(n1, n2) = heapq.heappop(max_heap)
			(x, y) = heapq.heappop(max_heap)
			n1 = -n1
			x = -x
			s1 += n2 + y
			n1 -= 1
			x -= 1
			if n1 > 0:
				heapq.heappush(max_heap, (-n1, n2))
			if x > 0:
				heapq.heappush(max_heap, (-x, y))
		if len(max_heap) > 0:
			(a, b) = heapq.heappop(max_heap)
			a = -a
			if a > 1:
				return '-1'
			else:
				s1 += b
		return s1


class Solution:

	def rearrangeString(self, s):
		if len(s) == 0:
			return -1
		count = [0] * 26
		n = len(count)
		res = [None] * len(s)
		for i in s:
			count[ord(i) - ord('a')] += 1
		max = 0
		for i in range(n):
			if max < count[i]:
				max = count[i]
				ch = chr(i + ord('a'))
		if max > (len(s) + 1) // 2:
			return '-1'
		ind = 0
		while max:
			res[ind] = ch
			ind += 2
			max -= 1
		count[ord(ch) - ord('a')] = 0
		for i in range(n):
			while count[i] > 0:
				if ind >= len(s):
					ind = 1
				res[ind] = chr(i + ord('a'))
				ind += 2
				count[i] -= 1
		return ''.join(res)


class Solution:

	def getMaxCountChar(self, count):
		maxCount = 0
		for i in range(26):
			if count[i] > maxCount:
				maxCount = count[i]
				maxChar = chr(i + ord('a'))
		return (maxCount, maxChar)

	def rearrangeString(self, S):
		N = len(S)
		if not N:
			return [-1]
		count = [0] * 26
		for char in S:
			count[ord(char) - ord('a')] += 1
		(maxCount, maxChar) = self.getMaxCountChar(count)
		if maxCount > (N + 1) // 2:
			return [-1]
		res = [None] * N
		ind = 0
		while maxCount:
			res[ind] = maxChar
			ind += 2
			maxCount -= 1
		count[ord(maxChar) - ord('a')] = 0
		for i in range(26):
			while count[i] > 0:
				if ind >= N:
					ind = 1
				res[ind] = chr(i + ord('a'))
				ind += 2
				count[i] -= 1
		return ''.join(res)


import heapq

class Solution:

	def rearrangeString(self, str):
		dict = {}
		for i in str:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		heap = []
		for i in dict:
			heapq.heappush(heap, [-dict[i], i])
		s = ''
		while len(heap) > 1:
			a = heapq.heappop(heap)
			b = heapq.heappop(heap)
			frequency1 = a[0]
			element1 = a[1]
			frequency2 = b[0]
			element2 = b[1]
			s += element1 + element2
			frequency1 += 1
			frequency2 += 1
			if frequency1 >= 0:
				pass
			else:
				heapq.heappush(heap, [frequency1, element1])
			if frequency2 >= 0:
				pass
			else:
				heapq.heappush(heap, [frequency2, element2])
		if len(heap) > 0:
			x = heapq.heappop(heap)
			element = x[1]
			frequency = x[0]
			if abs(frequency) > 1:
				return '0'
			else:
				s += element
		return s


from collections import defaultdict
import heapq

class Solution:

	def rearrangeString(self, st):
		d = defaultdict(int)
		for i in st:
			d[i] += 1
		a = []
		for (key, value) in d.items():
			a.append([-value, key])
		heapq.heapify(a)
		prev = [0, '#']
		ans = ''
		while a:
			char = heapq.heappop(a)
			ans = ans + char[1]
			char[0] += 1
			if prev[0] < 0:
				heapq.heappush(a, prev)
			prev = char
		return ans if len(ans) == len(st) else '-1'


import heapq as hq

class Solution:

	def rearrangeString(self, st):
		d = {}
		for i in range(len(st)):
			if st[i] in d:
				d[st[i]] += 1
			else:
				d[st[i]] = 1
		l = []
		for i in d:
			l.append([i, d[i]])
		heap = []
		for i in l:
			hq.heappush(heap, (-i[1], i[0]))
		s = ''
		while len(heap) > 1:
			(count1, char1) = hq.heappop(heap)
			(count2, char2) = hq.heappop(heap)
			s += char1 + char2
			if count1 < -1:
				hq.heappush(heap, (count1 + 1, char1))
			if count2 < -1:
				hq.heappush(heap, (count2 + 1, char2))
		if len(heap) == 1:
			(count, char) = hq.heappop(heap)
			if count < -1:
				return ''
			else:
				s += char
		return s


import string
import heapq

class Solution:

	def rearrangeString(self, str):
		memo = {}
		for i in range(len(str)):
			memo[str[i]] = memo.get(str[i], 0) + 1
		heap = []
		for (k, v) in memo.items():
			heap.append([-v, k])
		heapq.heapify(heap)
		ans = ''
		while len(heap) > 1:
			(k1, v1) = heapq.heappop(heap)
			(k2, v2) = heapq.heappop(heap)
			ans += v1 + v2
			k1 += 1
			if k1 != 0:
				heapq.heappush(heap, [k1, v1])
			k2 += 1
			if k2 != 0:
				heapq.heappush(heap, [k2, v2])
		if len(heap) == 1:
			(k, v) = heapq.heappop(heap)
			for i in range(-k):
				ans += v
		return ans


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, stre):
		n = len(stre)
		hmap = Counter(stre)
		ans = [(-j, i) for (i, j) in hmap.items()]
		heapq.heapify(ans)
		temp = ans[0][0] * -1
		if temp > (n + 1) // 2:
			return '-1'
		res = [''] * n
		i = 0
		while ans:
			(temp, k) = heapq.heappop(ans)
			temp = -1 * temp
			for _ in range(temp):
				res[i] = k
				i += 2
				if i >= n:
					i = 1
		return res


def rearrange_characters(input_string: str):
	n = len(input_string)
	dict_value = {}
	for i in range(0, n):
		if input_string[i] in dict_value:
			dict_value[input_string[i]] = dict_value[input_string[i]] + 1
		else:
			dict_value[input_string[i]] = 1
	sorted_count_list = sorted(dict_value, key=dict_value.get, reverse=True)
	i = 0
	start = 0
	char_list = list(input_string)
	while len(sorted_count_list) > 0:
		char = sorted_count_list.pop(0)
		count = dict_value[char]
		if count > n / 2 + 1:
			return '-1'
		start = start + 1
		for k in range(0, count):
			char_list[i] = char
			i = i + 2
			if i >= n:
				i = 1
	return ''.join(char_list)

class Solution:

	def rearrangeString(self, str):
		return rearrange_characters(str)


from heapq import heappop, heappush
from collections import Counter

class Solution:

	def rearrangeString(self, str):
		if len(str) == 1:
			return str
		count = Counter(list(str))
		heap = []
		for key in count.keys():
			heappush(heap, [-count[key], key])
		ans = ''
		while len(heap) > 1:
			most = heappop(heap)
			s_most = heappop(heap)
			ans += most[1] + s_most[1]
			most[0] += 1
			s_most[0] += 1
			if most[0]:
				heappush(heap, most)
			if s_most[0]:
				heappush(heap, s_most)
		if heap:
			if heap[0][0] < -1:
				return '-1'
			return ans + heap[0][1]
		return ans


class Solution:

	def rearrangeString(self, str):
		countArray = [0] * 26
		n = len(str)
		for i in str:
			countArray[ord(i) - ord('a')] += 1
		c = self.getMaxCountChar(countArray)
		maxCount = countArray[ord(c) - ord('a')]
		if maxCount > (n + 1) / 2:
			return ''
		res = [''] * n
		idx = 0
		while maxCount:
			res[idx] = c
			idx += 2
			maxCount -= 1
		countArray[ord(c) - ord('a')] = 0
		for i in range(26):
			while countArray[i] > 0:
				if idx >= n:
					idx = 1
				res[idx] = chr(ord('a') + i)
				idx += 2
				countArray[i] -= 1
		return ''.join(res)

	def getMaxCountChar(self, countArray):
		max = 0
		ch = ''
		for i in range(26):
			if countArray[i] > max:
				max = countArray[i]
				ch = chr(i + ord('a'))
		return ch


class Solution:

	def rearrangeString(self, str):
		d = dict()
		for i in str:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
		l = sorted(d.items(), key=lambda x: x[1], reverse=True)
		(k, v) = l[0]
		if v > (len(str) + 1) / 2:
			return ''
		i = 0
		freq = 0
		arr = [0] * len(str)
		while i < len(str):
			if freq == 0:
				(k, freq) = l.pop(0)
			arr[i] = k
			freq -= 1
			i += 2
		i = 1
		while i < len(str):
			if freq == 0:
				(k, freq) = l.pop(0)
			arr[i] = k
			freq -= 1
			i += 2
		return ''.join(arr)


import heapq

class Solution:

	def rearrangeString(self, S):
		count = {}
		for c in S:
			count[c] = 0
		for c in S:
			count[c] += 1
		heap = []
		for (key, value) in count.items():
			heap.append([-value, key])
		heapq.heapify(heap)
		prev = [0, '#']
		ans = ''
		while len(heap) != 0:
			key2 = heapq.heappop(heap)
			ans += key2[1]
			if -prev[0] > 0:
				heapq.heappush(heap, prev)
			key2[0] += 1
			prev = key2
		if len(ans) == len(S):
			return ans
		else:
			return '-1'


import heapq

class Solution:

	def rearrangeString(self, str):
		dict = {}
		for i in str:
			if i not in dict:
				dict[i] = 1
			else:
				dict[i] += 1
		heap = []
		ans = ''
		for i in dict:
			heapq.heappush(heap, (-dict[i], i))
		while len(heap) > 1:
			(f1, c1) = heapq.heappop(heap)
			(f2, c2) = heapq.heappop(heap)
			ans += c1
			ans += c2
			if abs(f1) > 1:
				heapq.heappush(heap, (f1 + 1, c1))
			if abs(f2) > 1:
				heapq.heappush(heap, (f2 + 1, c2))
		if len(heap) > 0:
			(f, c) = heap[0]
			if abs(f) > 1:
				return ''
			else:
				ans += c
		return ans


import heapq

class Solution:

	def rearrangeString(self, str):
		if not str:
			return
		d = {}
		for i in str:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		h = []
		for i in d:
			heapq.heappush(h, (-d[i], i))
		res = ''
		while len(h) > 1:
			(f1, c1) = heapq.heappop(h)
			(f2, c2) = heapq.heappop(h)
			res += c1
			res += c2
			if abs(f1) > 1:
				heapq.heappush(h, (f1 + 1, c1))
			if abs(f2) > 1:
				heapq.heappush(h, (f2 + 1, c2))
		if h:
			(f, c) = h[0]
			if abs(f) > 1:
				return ''
			else:
				res += c
		return res


class Solution:

	def rearrangeString(self, s):
		n = len(s)
		a = ord('a')
		mem = {}
		for c in s:
			if c in mem:
				mem[c] += 1
			else:
				mem[c] = 1
		l = list(mem)
		l.sort(key=lambda c: -mem[c])
		if mem[l[0]] > n // 2 + 1:
			return '-1'
		ss = [0] * n
		li = 0
		for start in range(2):
			i = start
			while i < n:
				ss[i] = l[li]
				mem[l[li]] -= 1
				if mem[l[li]] <= 0:
					li += 1
				i += 2
		return ''.join(ss)


class Solution:

	def rearrangeString(self, str):
		M = [0] * 26
		maxc = str[0]
		maxi = 0
		for i in range(len(str)):
			M[ord(str[i]) - ord('a')] += 1
			if maxi < M[ord(str[i]) - ord('a')]:
				maxi = M[ord(str[i]) - ord('a')]
				maxc = str[i]
		if maxi > (len(str) + 1) // 2:
			return str
		k = 0
		s = [None] * len(str)
		while maxi:
			s[k] = maxc
			k = k + 2
			maxi = maxi - 1
		M[ord(maxc) - ord('a')] = 0
		for i in range(26):
			while M[i] > 0:
				if k >= len(str):
					k = 1
				s[k] = chr(i + 97)
				k = k + 2
				M[i] -= 1
		ans = ''.join(s)
		return ans


from collections import deque

class Solution:

	def rearrangeString(self, str):
		n = len(str)
		if n == 1:
			return str
		counter = {c: 0 for c in str}
		for c in str:
			counter[c] += 1
		counter = [[c, count] for (c, count) in counter.items()]
		counter.sort(key=lambda x: x[1], reverse=True)
		arr = [''] * n
		(k, m) = (0, len(counter))
		Q = deque()
		for i in range(n):
			Q.append(i)
		while Q:
			tempQ = deque()
			fail = True
			while Q:
				p = Q.popleft()
				if p == 0:
					if arr[p + 1] != counter[k][0]:
						arr[p] = counter[k][0]
						counter[k][1] -= 1
						if counter[k][1] == 0:
							k += 1
						fail = False
					else:
						tempQ.append(p)
				elif p == n - 1:
					if arr[p - 1] != counter[k][0]:
						arr[p] = counter[k][0]
						counter[k][1] -= 1
						if counter[k][1] == 0:
							k += 1
						fail = False
					else:
						tempQ.append(p)
				elif arr[p - 1] != counter[k][0] and arr[p + 1] != counter[k][0]:
					arr[p] = counter[k][0]
					counter[k][1] -= 1
					if counter[k][1] == 0:
						k += 1
					fail = False
				else:
					tempQ.append(p)
			if fail:
				return '-1'
			Q = tempQ
		return ''.join(arr)


from collections import Counter
import heapq as hq

class Solution:

	def rearrangeString(self, s):
		count = Counter(s)
		max_heap = []
		res = ''
		for (char, freq) in count.items():
			hq.heappush(max_heap, (-freq, char))
		(oldFreq, oldChar) = (max_heap[0][0], max_heap[0][1])
		while max_heap:
			(topFreq, topChar) = hq.heappop(max_heap)
			res = res + topChar
			if oldChar != topChar and oldFreq != 0:
				hq.heappush(max_heap, (oldFreq, oldChar))
			(oldFreq, oldChar) = (topFreq + 1, topChar)
		return res


import heapq

class Solution:

	def rearrangeString(self, str):
		let = {}
		for i in str:
			if i in let:
				let[i] += 1
			else:
				let[i] = 1
		stk = []
		for (w, c) in let.items():
			stk.append([-1 * c, w])
		heapq.heapify(stk)
		ans = ''
		prev = None
		pc = 0
		while stk:
			(c, w) = heapq.heappop(stk)
			ans += w
			c += 1
			if prev:
				heapq.heappush(stk, [pc, prev])
			if c < 0:
				prev = w
				pc = c
			else:
				pc = 0
				prev = None
		return ans


class Solution:

	def rearrangeString(self, str):
		uniquecount = 0
		maxcount = 0
		d = {}
		for ele in str:
			if ele in d:
				d[ele] += 1
			else:
				d[ele] = 1
		for key in d:
			if d[key] > maxcount:
				maxcount = d[key]
				maxkey = key
		if maxcount > int((len(str) + 1) / 2):
			return '-1'
		res = [0] * len(str)
		idx = 0
		while maxcount != 0:
			res[idx] = maxkey
			idx += 2
			maxcount -= 1
		d[maxkey] = 0
		for i in range(len(str)):
			while d[str[i]] > 0:
				if idx >= len(str):
					idx = 1
				res[idx] = str[i]
				idx += 2
				d[str[i]] -= 1
		return ''.join(res)


class Solution:

	def rearrangeString(self, str):
		from heapq import heappush, heappop
		n = len(str)
		if not n:
			return -1
		d = {}
		for i in range(len(str)):
			if str[i] in d:
				d[str[i]] += 1
			else:
				d[str[i]] = 1
		max_heap = []
		for i in d:
			heappush(max_heap, [-d[i], i])
		max_heap2 = []
		while max_heap:
			heappush(max_heap2, [max_heap[0][0], max_heap[0][1]])
			heappop(max_heap)
		arr = [0 for i in range(n)]
		j = 0
		for i in max_heap2:
			number = -i[0]
			while number != 0:
				arr[j] = i[1]
				number -= 1
				if j == n - 1 or j == n - 2:
					j = 1
				else:
					j += 2
		str1 = ''.join(arr)
		return str1


import heapq

class Solution:

	def rearrangeString(self, str):
		d = {}
		for i in str:
			d[i] = 1 + d.get(i, 0)
		heap = []
		for key in d:
			heap.append([d[key], key])
		heapq._heapify_max(heap)
		final = ''
		while heap:
			t = heapq._heappop_max(heap)
			if t[0] == 0:
				break
			if final == '':
				final += t[1]
				heap.append([t[0] - 1, t[1]])
				heapq._siftdown_max(heap, 0, len(heap) - 1)
			elif t[1] == final[-1]:
				if heap:
					t2 = heapq._heappop_max(heap)
					if t2[0] == 0:
						break
					final += t2[1]
					heap.append([t2[0] - 1, t2[1]])
					heapq._siftdown_max(heap, 0, len(heap) - 1)
					heap.append([t[0], t[1]])
					heapq._siftdown_max(heap, 0, len(heap) - 1)
				else:
					break
			else:
				final += t[1]
				heap.append([t[0] - 1, t[1]])
				heapq._siftdown_max(heap, 0, len(heap) - 1)
		if len(final) == len(str):
			return final
		return '-1'


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, str):
		dic = Counter(str)
		max_hp = []
		for (char, cnt) in dic.items():
			heapq.heappush(max_hp, (-cnt, char))
		res = ''
		while max_hp:
			if len(max_hp) > 1:
				(f_cnt, f_char) = heapq.heappop(max_hp)
				res += f_char
				(s_cnt, s_char) = heapq.heappop(max_hp)
				res += s_char
				f_cnt += 1
				s_cnt += 1
				if f_cnt < 0:
					heapq.heappush(max_hp, (f_cnt, f_char))
				if s_cnt < 0:
					heapq.heappush(max_hp, (s_cnt, s_char))
			else:
				(f_cnt, f_char) = heapq.heappop(max_hp)
				if f_cnt == -1:
					res += f_char
				else:
					return ''
		return res


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, s):
		c = Counter(s)
		hp = [(-val, key) for (key, val) in c.items()]
		heapq.heapify(hp)
		res = ''
		while hp:
			(a_val, a) = heapq.heappop(hp)
			(b_val, b) = heapq.heappop(hp) if hp else (-1, '')
			if res and a == res[-1]:
				return ''
			res += a
			a_val += 1
			if a_val:
				heapq.heappush(hp, (a_val, a))
			res += b
			b_val += 1
			if b_val:
				heapq.heappush(hp, (b_val, b))
		return res


from heapq import heappush, heappop

class Solution:

	def rearrangeString(self, str):
		q = []
		d = {}
		for i in str:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			heappush(q, [-d[i], i])
		ans = ''
		while len(q) > 1:
			(c1, ele1) = heappop(q)
			(c2, ele2) = heappop(q)
			ans += ele1 + ele2
			if c1 + 1 < 0:
				heappush(q, [c1 + 1, ele1])
			if c2 + 1 < 0:
				heappush(q, [c2 + 1, ele2])
		if q:
			(val, ele) = heappop(q)
			ans += ele
		return ans


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, s):
		n = len(s)
		c = Counter(s)
		if (c.most_common()[0][1] - 1) * 2 >= n:
			return '-1'
		heap = [(-item[1], item[0]) for item in c.items()]
		heapq.heapify(heap)
		output = ''
		count = 0
		while heap:
			if count:
				(count, item) = heapq.heapreplace(heap, (count, item))
			else:
				(count, item) = heapq.heappop(heap)
			output += item
			count += 1
		return output


import heapq

class Solution:

	def rearrangeString(self, str):
		map_s = {}
		str = str.strip()
		n = 0
		for i in str:
			if i in map_s:
				map_s[i] += 1
			else:
				map_s[i] = 1
			n += 1
		r = [''] * n
		hq = []
		for (k, v) in map_s.items():
			heapq.heappush(hq, (-1 * v, k))
		i = 0
		while i < n and hq:
			top = heapq.heappop(hq)
			(v, k) = top
			v = -1 * v
			if v > (n + 1) // 2:
				return '-1'
			while v and i < n:
				r[i] = k
				v -= 1
				i += 2
		i = 1
		while v and i < n:
			r[i] = k
			v -= 1
			i += 2
		while i < n and hq:
			top = heapq.heappop(hq)
			(v, k) = top
			v = -1 * v
			while v:
				r[i] = k
				v -= 1
				i += 2
		return ''.join(r)


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, str):
		d = Counter(str)
		heap = []
		for i in d:
			heapq.heappush(heap, (-1 * d[i], i))
		s = ''
		while len(heap) > 1:
			(cnt1, ch1) = heapq.heappop(heap)
			(cnt2, ch2) = heapq.heappop(heap)
			s += ch1 + ch2
			if cnt1 < -1:
				heapq.heappush(heap, (cnt1 + 1, ch1))
			if cnt2 < -1:
				heapq.heappush(heap, (cnt2 + 1, ch2))
		if len(heap) == 1:
			(cnt, char) = heapq.heappop(heap)
			if cnt < -1:
				return ''
			else:
				s += char
		return s


class Solution:

	def rearrangeString(self, str):
		n = len(str)
		if n == 1:
			return str
		d = {}
		for i in str:
			d[i] = d.get(i, 0) + 1
		dd = []
		for i in d:
			dd.append([i, d[i]])
			if d[i] > (n + 1) / 2:
				return '-1'
		dd.sort(key=lambda x: -x[1])
		i = 0
		ans = ['' for i in range(n)]
		while i < n:
			temp = dd.pop(0)
			(val, cnt) = (temp[0], temp[1])
			while i < n and cnt > 0:
				ans[i] = val
				cnt -= 1
				i += 2
			if cnt != 0:
				dd = [[val, cnt]] + dd
		i = 1
		while i < n:
			temp = dd.pop(0)
			(val, cnt) = (temp[0], temp[1])
			while i < n and cnt > 0:
				ans[i] = val
				cnt -= 1
				i += 2
		return ''.join(ans)


class Solution:

	def rearrangeString(self, s):
		dt = {}
		res = [-1 for i in range(len(s))]
		for i in range(len(s)):
			dt[s[i]] = 1 + dt.get(s[i], 0)
		cmax = max(zip(dt.values(), dt.keys()))[1]
		if dt[cmax] > (len(s) + 1) // 2:
			return ''
		idx = 0
		nmax = dt[cmax]
		for i in range(0, nmax):
			res[idx] = cmax
			idx += 2
			nmax -= 1
		dt[cmax] = 0
		for i in range(26):
			for k in dt.keys():
				while dt[k] > 0:
					if idx >= len(s):
						idx = 1
					res[idx] = k
					idx += 2
					dt[k] -= 1
		return ''.join(res)


import heapq

class Solution:

	def rearrangeString(self, S):
		freq = {}
		for c in S:
			freq[c] = freq.get(c, 0) + 1
		heap = [(-f, c) for (c, f) in freq.items()]
		heapq.heapify(heap)
		result = []
		while heap:
			(f, c) = heapq.heappop(heap)
			if result and result[-1] == c:
				if not heap:
					return ''
				(f2, c2) = heapq.heappop(heap)
				result.append(c2)
				heapq.heappush(heap, (f, c))
				if f2 < -1:
					heapq.heappush(heap, (f2 + 1, c2))
			else:
				result.append(c)
				if f < -1:
					heapq.heappush(heap, (f + 1, c))
		return ''.join(result)


import heapq

class Solution:

	def rearrangeString(self, str):
		if len(str) == 0 or len(str) == 1:
			return str
		res = []
		d = {}
		heap = []
		for s in str:
			if s in d:
				d[s] += 1
			else:
				d[s] = 1
		for keys in d:
			heap.append((-d[keys], keys))
		heapq.heapify(heap)
		while len(heap) >= 2:
			(tc, t) = heapq.heappop(heap)
			(nc, n) = heapq.heappop(heap)
			res.append(t)
			res.append(n)
			tc += 1
			nc += 1
			if tc:
				heapq.heappush(heap, (tc, t))
			if nc:
				heapq.heappush(heap, (nc, n))
		if len(heap) != 0:
			(c, e) = heapq.heappop(heap)
			if c < -1:
				return '-1'
			if res[-1] == e:
				return '-1'
			else:
				res.append(e)
		return ''.join(res)


class Solution:

	def rearrangeString(self, strg):
		dic = {}
		n = len(strg)
		for i in strg:
			dic[i] = dic.get(i, 0) + 1
		a = sorted(dic.items(), key=lambda x: x[1], reverse=True)
		if a[0][1] > n // 2 + 1:
			return '-1'
		solution = [0] * len(strg)
		cur_char_idx = 0
		i = 0
		while i < n:
			if dic[a[cur_char_idx][0]] <= 0:
				cur_char_idx += 1
			if cur_char_idx >= len(a):
				break
			cur_char = a[cur_char_idx][0]
			dic[a[cur_char_idx][0]] -= 1
			solution[i] = cur_char
			i += 2
			if i >= n:
				i = 1
		return solution


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, s):
		count = Counter(s)
		maxheap = [[-cnt, char] for (char, cnt) in count.items()]
		heapq.heapify(maxheap)
		prev = None
		res = ''
		while maxheap or prev:
			if prev and (not maxheap):
				return ''
			(cnt, char) = heapq.heappop(maxheap)
			res += char
			cnt += 1
			if prev:
				heapq.heappush(maxheap, prev)
				prev = None
			if cnt != 0:
				prev = [cnt, char]
		return res if len(res) == len(s) else '-1'


class Solution:

	def rearrangeString(self, str):
		str = [ch for ch in str]
		b = [0] * len(str)
		dict = []
		str.sort()
		t = str[0]
		for i in range(1, len(str)):
			if str[i] == str[i - 1]:
				t += str[i]
			else:
				dict.append(t)
				t = str[i]
		if len(dict) > 0 and dict[-1] != t:
			dict.append(t)
		elif len(dict) == 0:
			dict.append(t)
		dict.sort(key=lambda el: len(el), reverse=True)
		str = ''.join(dict)
		i = 0
		j = 0
		while i < len(str):
			b[j] = str[i]
			i += 1
			j += 2
			if j >= len(str):
				j = 1
		for i in range(1, len(b)):
			if b[i] == b[i - 1]:
				return '-1'
		return ''.join(b)


class Solution:

	def rearrangeString(self, str):
		dict = {}
		lis = [0] * len(str)
		for i in str:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		j = 0
		b = 1
		for i in dict:
			a = dict.get(i)
			for k in range(a):
				if j >= len(str) and b < len(str):
					lis[b] = i
					b += 2
				else:
					lis[j] = i
					j += 2
		c = ''.join(lis)
		if len(c) != len(str):
			return -1
		return c


import heapq
from collections import Counter

class Solution:

	def rearrangeString(self, s):
		count = Counter(s)
		h = []
		heapq.heapify(h)
		for (char, cnt) in count.items():
			heapq.heappush(h, [-cnt, char])
		prev = None
		ans = ''
		while h or prev:
			if prev and (not h):
				return '-1'
			(cnt, char) = heapq.heappop(h)
			ans += char
			cnt += 1
			if prev:
				heapq.heappush(h, prev)
				prev = None
			if cnt != 0:
				prev = [cnt, char]
		return ans


import sys

class Solution:

	def rearrangeString(self, str):
		d = {}
		maxf = -sys.maxsize
		n = len(str)
		for i in range(n):
			d[str[i]] = d.get(str[i], 0) + 1
			if d[str[i]] > maxf:
				maxf = d[str[i]]
				maxc = str[i]
		if maxf > (n + 1) // 2:
			return '-1'
		arr = [0 for i in range(n)]
		ep = 0
		while ep < n:
			if maxf != 0:
				arr[ep] = maxc
				ep += 2
				maxf -= 1
			else:
				break
		od = 1
		for ele in d:
			if ele != maxc:
				while d[ele] != 0:
					if ep < n:
						arr[ep] = ele
						ep += 2
					else:
						arr[od] = ele
						od += 2
					d[ele] -= 1
		arr = ''.join(arr)
		return arr


class Solution:

	def rearrangeString(self, s):
		import heapq
		base = ord('a')
		M = [[0, chr(i + base)] for i in range(26)]
		base = ord('a')
		for c in s:
			ci = ord(c) - base
			M[ci][0] -= 1
		heapq.heapify(M)
		ans = []
		tmp = None
		while len(M) > 0:
			larg = heapq.heappop(M)
			(freq, c) = larg
			if freq == 0:
				break
			if len(ans) == 0:
				ans.append(c)
			elif c != ans[-1]:
				ans.append(c)
			else:
				return '-1'
			if tmp is not None and tmp[0] < 0:
				heapq.heappush(M, tmp)
			tmp = larg
			tmp[0] += 1
		ans = ''.join(ans)
		return ans


class Solution:

	def rearrangeString(self, str):
		count = [0] * 26

		def getMaxChar(count):
			max_ = 0
			ch = ''
			for (j, i) in enumerate(count):
				if i > max_:
					max_ = i
					ch = ord('a') + j
			return chr(ch)
		for i in str:
			count[ord(i) - ord('a')] += 1
		max_ch = getMaxChar(count)
		max_count = count[ord(max_ch) - ord('a')]
		if max_count > (len(str) + 1) // 2:
			return '-1'
		result = ['0'] * len(str)
		idx = 0
		while max_count:
			result[idx] = max_ch
			idx += 2
			max_count -= 1
		count[ord(max_ch) - ord('a')] = 0
		for (j, i) in enumerate(count):
			while i > 0:
				idx = 1 if idx >= len(str) else idx
				result[idx] = chr(j + ord('a'))
				idx += 2
				i -= 1
		return result


class Solution:

	def rearrangeString(self, str):
		hash = {}
		n = len(str)
		for i in range(n):
			if str[i] in hash:
				hash[str[i]] += 1
			else:
				hash[str[i]] = 1
		res = [''] * n
		hash_list = []
		for key in hash.keys():
			hash_list.append([hash[key], key])
		i = 0
		j = 1
		hash_list.sort(reverse=True)
		front = hash_list[0]
		m = len(hash_list)
		while i < n:
			res[i] = front[1]
			front[0] -= 1
			if front[0] == 0 and j < m:
				front = hash_list[j]
				j += 1
			i += 2
		i = 1
		while i < n:
			res[i] = front[1]
			front[0] -= 1
			if front[0] == 0 and j < m:
				front = hash_list[j]
				j += 1
			i += 2
		return ''.join(res)


import heapq

class Solution:

	def rearrangeString(self, s):
		d = {}
		for x in s:
			if x in d:
				d[x] += 1
			else:
				d[x] = 1
		heap = [[-d[x], x] for x in d]
		heapq.heapify(heap)
		ans = []
		while len(heap) > 0:
			top1 = heapq.heappop(heap)
			if len(heap) == 0:
				ans.append(top1[1])
				break
			top2 = heapq.heappop(heap)
			ans.append(top1[1])
			ans.append(top2[1])
			if top1[0] < -1:
				heapq.heappush(heap, [top1[0] + 1, top1[1]])
			if top2[0] < -1:
				heapq.heappush(heap, [top2[0] + 1, top2[1]])
		return ''.join(ans)


from collections import Counter

class Solution:

	def rearrangeString(self, strr):
		myCounter = Counter(strr)
		self.newWord = []
		allCounter = list(map(lambda x: (x[0], x[1]), myCounter.most_common(len(strr))))
		maxx = allCounter[0]
		prev = None
		i = 1
		while i < len(allCounter):
			minn = allCounter[i]
			if prev is None or maxx[0] == prev[0]:
				prev = maxx
				maxx = self.fillWord(*maxx, *minn)
			else:
				prev = minn
				maxx = self.fillWord(*minn, *maxx)
			if maxx[0] is None:
				prev = None
				try:
					maxx = allCounter[i + 1]
					i += 2
				except:
					break
			else:
				i += 1
		if maxx[0] is None:
			return ''.join(self.newWord)
		maxx = list(maxx[0]) * maxx[1]
		i = 0
		while i < len(self.newWord) and maxx:
			if i == 0 and self.newWord[i] != maxx[0]:
				self.newWord.insert(0, maxx.pop())
				i += 2
			elif self.newWord[i - 1] != maxx[0] and self.newWord[i] != maxx[0]:
				self.newWord.insert(i, maxx.pop())
				i += 2
			else:
				i += 1
		if maxx and i == len(self.newWord) and (len(maxx) == 1) and (self.newWord[i - 1] != maxx[0]):
			self.newWord.insert(i, maxx.pop())
		if maxx:
			return '-1'
		return ''.join(self.newWord)

	def fillWord(self, maxx, maxCount, minn, minCount):
		if maxCount < minCount:
			minLen = maxCount
			toReturn = (minn, minCount - minLen)
		elif maxCount > minCount:
			minLen = minCount
			toReturn = (maxx, maxCount - minLen)
		else:
			minLen = maxCount
			toReturn = (None, None)
		self.newWord += [maxx, minn] * minLen
		return toReturn


from heapq import heapify, heappush, heappop

class Solution:

	def rearrangeString(self, s):
		a1 = {}
		for i in s:
			if i not in a1:
				a1[i] = 0
			a1[i] += 1
		d = []
		heapify(d)
		for i in a1:
			heappush(d, [-a1[i], i])
		s = ''
		while len(d) > 0:
			x = heappop(d)
			s += x[1]
			x[0] += 1
			if len(d) > 0:
				y = heappop(d)
				s += y[1]
				y[0] += 1
				if y[0] < 0:
					heappush(d, y)
			elif x[0] < 0:
				return '-1'
			if x[0] < 0:
				heappush(d, x)
		return s


import heapq

class Solution:

	def rearrangeString(self, str):
		s = str
		n = len(s)
		arr = [0 for i in range(26)]
		ma = 0
		for i in s:
			arr[int(ord(i)) - int(ord('a'))] += 1
		if max(arr) > (n + 1) // 2:
			return s
		else:
			hq = []
			heapq.heapify(hq)
			for i in range(26):
				heapq.heappush(hq, [-1 * arr[i], i])
			ans = ''
			i = 0
			while i < n:
				a = heapq.heappop(hq)
				b = heapq.heappop(hq)
				a1 = a[0] * -1
				a2 = chr(a[1] + int(ord('a')))
				b1 = b[0] * -1
				b2 = chr(b[1] + int(ord('a')))
				if a1 > 0:
					ans += a2
					a1 -= 1
				else:
					break
				if b1 > 0:
					ans += b2
					b1 -= 1
				else:
					break
				heapq.heappush(hq, [-1 * a1, a[1]])
				heapq.heappush(hq, [-1 * b1, b[1]])
				i += 2
			return ans


from heapq import heappush, heappop

class Solution:

	def rearrangeString(self, str):
		temp2 = None
		dic = {}
		heap = []
		n = len(str)
		s = ''
		for i in range(n):
			if str[i] in dic:
				dic[str[i]] += 1
			else:
				dic[str[i]] = 1
		for (key, values) in dic.items():
			heappush(heap, [-values, key])
		while len(heap) > 0:
			temp1 = heappop(heap)
			s += temp1[1]
			temp1[0] += 1
			if temp2 != None and temp2[0] != 0:
				heappush(heap, temp2)
			temp2 = temp1
		return s


from collections import Counter
from heapq import *

class Solution:

	def rearrangeString(self, s):
		heap = []
		has = Counter(s)
		for (key, value) in has.items():
			heappush(heap, (-value, key))
		ans = ''
		prev = (None, '#')
		while heap:
			(freq, ch) = heappop(heap)
			freq = abs(freq)
			ans += ch
			if prev[0] and abs(prev[0]) > 0:
				heappush(heap, prev)
			freq -= 1
			prev = (-freq, ch)
		return ans


class Solution:

	def rearrangeString(self, s):
		freq = [0] * 26
		n = len(s)
		for i in s:
			asci = ord(i) - 97
			freq[asci] += 1
		count = []
		for (ind, val) in enumerate(freq):
			if val != 0:
				count.append([val, chr(ind + 97)])
		count.sort(reverse=True)
		if count and count[0][0] - 1 > n // 2:
			return ''
		ans = [''] * n
		start = 0
		for (k, val) in count:
			while k > 0:
				while ans[start] != '':
					start += 1
					start = start % n
				ans[start] = val
				start += 2
				start = start % n
				k -= 1
			start = start % n
		return ''.join(ans)


import heapq

class Solution:

	def rearrangeString(self, s):
		map1 = {}
		for i in s:
			if i in map1:
				map1[i] += 1
			else:
				map1[i] = 1
		heap = []
		for (key, value) in map1.items():
			heap.append([-value, key])
		heapq.heapify(heap)
		ansString = ''
		prev = [0, '$']
		while heap:
			ele = heapq.heappop(heap)
			ansString += ele[1]
			if prev[0] != 0:
				heapq.heappush(heap, prev)
			ele[0] += 1
			prev = ele
		if len(ansString) == len(s):
			return ansString
		return '-1'


class Solution:

	def getmax(self, countarray):
		maxi = 0
		ch = ''
		for i in range(26):
			if countarray[i] > maxi:
				maxi = countarray[i]
				ch = chr(i + ord('a'))
		return ch

	def rearrangeString(self, str):
		n = len(str)
		countarray = [0] * 26
		for i in str:
			countarray[ord(i) - ord('a')] += 1
		c = chr(countarray.index(max(countarray)) + ord('a'))
		maxcount = countarray[ord(c) - ord('a')]
		if maxcount > (n + 1) / 2:
			return ''
		res = [''] * n
		idx = 0
		while maxcount:
			res[idx] = c
			idx += 2
			maxcount -= 1
		countarray[ord(c) - ord('a')] = 0
		for i in range(26):
			while countarray[i] > 0:
				if idx >= n:
					idx = 1
				res[idx] = chr(ord('a') + i)
				idx += 2
				countarray[i] -= 1
		return ''.join(res)


def count(ls):
	maxCount = 0
	maxChar = ''
	for i in range(26):
		if maxCount < ls[i]:
			maxCount = ls[i]
			maxChar = chr(i + ord('a'))
	return (maxCount, maxChar)

class Solution:

	def rearrangeString(self, s):
		ls = [0] * 26
		st = set(s)
		if len(st) == 1:
			return s
		n = len(s)
		for i in range(n):
			ls[ord(s[i]) - ord('a')] += 1
		(maxcount, maxchar) = count(ls)
		if maxcount > (n + 1) // 2:
			return s
		ans = [None] * n
		idx = 0
		while maxcount:
			ans[idx] = maxchar
			idx += 2
			maxcount -= 1
		ls[ord(maxchar) - ord('a')] = 0
		for i in range(26):
			while ls[i] > 0:
				if idx >= n:
					idx = 1
				ans[idx] = chr(i + ord('a'))
				idx += 2
				ls[i] -= 1
		return ''.join(ans)