Given a string with repeated characters, the task is to complete the function rearrangeString which rearrange characters in a string so that no two adjacent characters are same.
Note : It may be assumed that the string has only lowercase English alphabets and such transformation is always always possible.
Example 1:
Input:
S = aaabc
Output: 1
Explanation: We can transform the string
to abaca.
Example 2:
Input:
S = aaabb
Output: 1
Explanation: We can transform the string
to ababa.
 
Your Task:
Complete the function rearrangeString() which takes a string as an input parameter and returns the rearranged string. (The output will be 1 if the returned string has no adjacent character same, otherwise 0. Printing is done by the driver's code.)
Expected Time Complexity: O(N * log N), N = length of the string.
Expected Auxiliary Space: O(constant)
Constraints:
1< N < 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: # your task is to complete this function

class Solution:
    # function should return the modified string
    def rearrangeString(self, string):
        # Code here


Solutions:
from heapq import *

class Solution:

	def rearrangeString(self, string):
		n = len(string)
		count = [0] * 26
		for i in range(n):
			count[ord(string[i]) - 97] += 1
		pq = []
		res = ''
		for i in range(97, 123):
			if count[i - 97] != 0:
				heappush(pq, [-1 * count[i - 97], chr(i)])
		prev = [1, '#']
		while pq != []:
			ky = heappop(pq)
			res = res + ky[1]
			if prev[0] < 0:
				heappush(pq, prev)
			ky[0] += 1
			prev = ky
		if len(res) != n:
			return '-1'
		return res


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

class Solution:

	def rearrangeString(self, S):
		N = len(S)
		if not N:
			return False
		count = [0] * 26
		for char in S:
			count[ord(char) - ord('a')] += 1
		(maxCount, maxChar) = getMaxCountChar(count)
		if maxCount > (N + 1) // 2:
			return False
		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)


from collections import defaultdict
import heapq

class Solution:

	def rearrangeString(self, string):
		n = len(string)
		if n == 1:
			return string
		store = defaultdict(lambda : 0)
		for item in string:
			store[item] += 1
		heap = []
		for (key, value) in store.items():
			heap.append((value, key))
		heapq._heapify_max(heap)
		output = ''
		(count, char) = heapq._heappop_max(heap)
		for _ in range(n):
			output += char
			count -= 1
			temp_count = count
			temp_char = char
			(count, char) = heapq._heapreplace_max(heap, (temp_count, temp_char))
		return output


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, string):
		dic = Counter(string)
		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


class Solution:

	def rearrangeString(self, string):
		import heapq
		heap = []
		from collections import defaultdict
		d = defaultdict(int)
		for i in string:
			d[i] += 1
		for i in d.keys():
			heapq.heappush(heap, (-d[i], i))
		news = ''
		prev = (0, '#')
		while heap:
			curr = heapq.heappop(heap)
			news += curr[1]
			curr = (curr[0] + 1, curr[1])
			if prev[0] < 0:
				heapq.heappush(heap, prev)
			prev = curr
		return news


from math import ceil

class Solution:

	def rearrangeString(self, string):
		n = len(string)
		count = [0] * 26
		for i in range(n):
			count[ord(string[i]) - ord('a')] += 1
		(max_char, max_char_freq) = self.getMax(count)
		if max_char_freq > ceil(len(string) / 2):
			return string
		idx = 0
		out = [None] * n
		while max_char_freq > 0:
			out[idx] = max_char
			max_char_freq -= 1
			idx += 2
		count[ord(max_char) - ord('a')] = 0
		for i in range(26):
			while count[i] > 0:
				if idx > n - 1:
					idx = 1
				out[idx] = chr(i + ord('a'))
				count[i] -= 1
				idx += 2
		return out

	def getMax(self, count):
		(max_char, max_char_freq) = ('a', count[0])
		for i in range(1, 26):
			if count[i] > max_char_freq:
				max_char_freq = count[i]
				max_char = chr(i + ord('a'))
		return (max_char, max_char_freq)


class Solution:

	def rearrangeString(self, string):
		n = len(string)
		if n == 0:
			return False
		count = [0] * 26
		for char in string:
			count[ord(char) - ord('a')] = count[ord(char) - ord('a')] + 1
		(maxCount, maxChar) = self.getMaxCharCount(count)
		if maxCount > (n + 1) // 2:
			return False
		res = [None] * n
		ind = 0
		while maxCount:
			res[ind] = maxChar
			ind = ind + 2
			maxCount = 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 = ind + 2
				count[i] = count[i] - 1
		return ''.join(res)

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


class Solution:

	def rearrangeString(self, string):
		n = len(string)
		if n == 1:
			return string
		d = {}
		l = []
		arr = [0] * n
		for i in string:
			d[i] = d.get(i, 0) + 1
		for (k, v) in d.items():
			l.append([k, v])
		l.sort(key=lambda x: x[1], reverse=True)
		i = 0
		cnt = 0
		key = l.pop(0)
		while cnt < n:
			j = i
			while j < n:
				if key[1]:
					arr[j] = key[0]
					cnt += 1
					j += 2
					key[1] -= 1
				else:
					key = l.pop(0)
			i += 1
		op = ''
		for i in arr:
			op += i
		return op


class Solution:

	def rearrangeString(self, string):
		char_arr = [0] * 26
		length = len(string)
		for val in string:
			char_arr[ord(val) - ord('a')] += 1
		max_char = 0
		max_count = 0
		for (i, val) in enumerate(char_arr):
			if val > max_count:
				max_count = val
				max_char = chr(i + ord('a'))
		if max_count > (length + 1) // 2:
			return ''
		index = 0
		result = [''] * length
		while max_count != 0 and index < length:
			result[index] = max_char
			index += 2
			max_count -= 1
		char_arr[ord(max_char) - ord('a')] = max_count
		for (i, val) in enumerate(char_arr):
			while val != 0:
				if index >= length:
					index = 1
				result[index] = chr(i + ord('a'))
				val -= 1
				index += 2
		return ''.join(result)


import heapq
from collections import Counter

class Solution:

	def rearrangeString(self, string: str) -> str:
		count = Counter(string)
		maxheap = [[-cnt, ch] for (ch, cnt) in count.items()]
		heapq.heapify(maxheap)
		prev = None
		result = ''
		while maxheap or prev:
			if not maxheap and prev:
				return ''
			(cnt, ch) = heapq.heappop(maxheap)
			cnt += 1
			result += ch
			if prev:
				heapq.heappush(maxheap, prev)
				prev = None
			if cnt != 0:
				prev = [cnt, ch]
		return result


class Solution:

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

	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)


import heapq

class Solution:

	def rearrangeString(self, string):
		charCount = {}
		heap = []
		prev = (0, 0)
		rearranged = []
		for char in string:
			if char not in charCount:
				charCount[char] = 0
			charCount[char] += 1
		for (char, count) in charCount.items():
			heapq.heappush(heap, (-1 * count, char))
		while len(heap):
			(currentCount, currentChar) = heapq.heappop(heap)
			rearranged.append(currentChar)
			if prev[0] != 0:
				heapq.heappush(heap, (prev[0], prev[1]))
			prev = (currentCount + 1, currentChar)
		return ''.join(rearranged)


from collections import Counter
import heapq

class Solution:

	def rearrangeString(self, string):
		ans = ''
		heap = []
		hmap = Counter(string)
		for (x, y) in hmap.items():
			heapq.heappush(heap, [-y, x])
		prev = None
		while heap:
			(f, ch) = heapq.heappop(heap)
			f *= -1
			ans += ch
			if prev != None and prev[0] != 0:
				heapq.heappush(heap, prev)
			prev = [-(f - 1), ch]
		return ans


class Solution:

	def get_max_count_char(self, string, count):
		max_count = 0
		max_char = None
		for i in range(26):
			if count[i] > max_count:
				max_count = count[i]
				max_char = chr(i + ord('a'))
		return (max_count, max_char)

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


import heapq

class Key:

	def __init__(self, character: str, freq: int) -> None:
		self.character = character
		self.freq = freq

	def __lt__(self, other: 'Key') -> bool:
		return self.freq > other.freq

class Solution:

	def rearrangeString(self, string):
		str = string
		n = len(str)
		fMap = dict()
		for i in str:
			fMap[ord(i) - ord('a')] = fMap.get(ord(i) - ord('a'), 0) + 1
		pq = []
		heapq.heapify(pq)
		for c in range(26):
			if fMap.get(c) is not None:
				heapq.heappush(pq, Key(chr(97 + c), fMap[c]))
		ans = ''
		block = heapq.heappop(pq)
		ans = ans + block.character
		block.freq -= 1
		while len(pq) > 0:
			temp = heapq.heappop(pq)
			ans = ans + temp.character
			temp.freq -= 1
			if block.freq > 0:
				heapq.heappush(pq, block)
			block = temp
		return ans


class Solution:

	def rearrangeString(self, string):
		d = {}
		for e in string:
			if e not in d:
				d[e] = 1
			else:
				d[e] += 1
		s = set(string)
		max_ = max(d.values())
		for e in d.keys():
			if d[e] == max_:
				val = e
				break
		if max_ > (len(string) + 1) // 2:
			return string
		a = [0] * len(string)
		i = 0
		while max_ != 0:
			a[i] = val
			i += 2
			max_ -= 1
			if i >= len(a):
				i = 1
		s.remove(val)
		for e in s:
			while d[e] != 0:
				a[i] = e
				d[e] -= 1
				i += 2
				if i >= len(a):
					i = 1
		x = ''.join(a)
		return x


class Solution:

	def rearrangeString(self, string):
		arr = [0 for i in range(len(string))]
		dic = {}
		for i in string:
			if i in dic.keys():
				dic[i][1] += 1
			else:
				dic[i] = [i, 1]
		temp = []
		for i in dic:
			temp.append(dic[i])
		temp.sort(key=lambda x: x[1], reverse=True)
		i = 0
		j = 0
		while j < len(temp):
			arr[i] = temp[j][0]
			temp[j][1] -= 1
			if temp[j][1] == 0:
				j += 1
			i += 2
			if i >= len(string):
				i = 1
		s = ''
		for i in arr:
			s += i
		return s


from heapq import heappop, heappush, heapify
from collections import defaultdict

class Solution:

	def rearrangeString(self, string):
		d = defaultdict()
		h = []
		ans = ''
		heapify(h)
		for i in string:
			if i not in d:
				d[i] = string.count(i)
				heappush(h, [d.get(i) * -1, i])
		q1 = heappop(h)
		ans += q1[1]
		q1[0] += 1
		while h:
			q2 = heappop(h)
			ans += q2[1]
			q2[0] += 1
			if q1[0] < 0:
				heappush(h, q1)
			q1 = q2
		while q1[0] > 0:
			ans += q1[1]
			q1[0] += 1
		return ans


from collections import defaultdict

class Solution:

	def rearrangeString(self, string):
		dic = defaultdict(lambda : 0)
		for i in range(len(string)):
			dic[string[i]] += 1
		dic1 = sorted(dic.items(), key=lambda kv: kv[1], reverse=True)
		dic2 = [list(ele) for ele in dic1]
		m = (len(string) + 1) // 2
		if dic2[0][1] > m:
			return
		string1 = [0] * len(string)
		(k, i, j) = (0, 0, 0)
		while j < 2:
			k = j
			while dic2[i][1] > 0 and k < len(string):
				string1[k] = dic2[i][0]
				dic2[i][1] -= 1
				k += 2
				if dic2[i][1] == 0 and i + 1 < len(dic2):
					i += 1
			j += 1
		s = ''
		for i in string1:
			s = s + i
		return s


class Solution:

	def rearrangeString(self, string):
		h = {}
		for i in string:
			h[i] = 1 + h.get(i, 0)
			if h[i] > (len(string) + 1) // 2:
				return string
		l = []
		h1 = {}
		m = float('-inf')
		for i in string:
			if h1.get(i, 0) == 0:
				l += [[h[i], i]]
				h1[i] = 1
		l.sort(reverse=True)
		s1 = ''
		for i in l:
			s1 += i[1] * i[0]
		l1 = [0] * len(string)
		i = 0
		while h[l[0][1]] != 0:
			l1[i] = l[0][1]
			h[l[0][1]] -= 1
			i += 2
		p = i
		if p >= len(string):
			p = 1
		for i in s1:
			if h[i] > 0:
				l1[p] = i
				p += 2
				if p >= len(string):
					p = 1
		s = ''
		for i in l1:
			s += i
		return s


from heapq import heappop, heappush, heapify
from collections import Counter

class Solution:

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


class Solution:

	def rearrangeString(self, string):
		res = list(string)
		d = dict()
		maxchar = None
		n = len(string)
		maxcount = 0
		for i in string:
			d[i] = d.get(i, 0) + 1
			if d[i] > maxcount:
				maxchar = i
				maxcount = d[i]
		if maxcount > (n + 1) // 2:
			print('hi')
			return '-1'
		i = 0
		while i < n and maxcount > 0:
			res[i] = maxchar
			maxcount -= 1
			i += 2
		d[maxchar] = 0
		pos = i
		for i in d:
			while d[i] > 0:
				if pos % 2 == 0 and pos >= n:
					pos = 1
				res[pos] = i
				d[i] -= 1
				pos += 2
		return ''.join(res)


class Solution:

	def rearrangeString(self, s):
		n = len(s)
		if n <= 1:
			return s
		d = {}
		for ele in s:
			d[ele] = d.get(ele, 0) + 1
		maxi = max(d.values())
		if maxi > n / 2 + 1:
			return ''
		for ele in d:
			if d[ele] == maxi:
				value = ele
				d[ele] = -1
				break
		ans = [0] * len(s)
		i = 0
		while maxi != 0:
			ans[i] = value
			i += 2
			maxi -= 1
		for ele in d:
			while d[ele] > 0:
				if i >= n:
					i = 1
				ans[i] = ele
				d[ele] -= 1
				i += 2
		return ''.join(ans)


class Solution:

	def rearrangeString(self, string):
		n = len(string)
		d = [0] * 26
		maxa = -1 << 32
		for i in string:
			d[ord(i) - 97] += 1
		for i in range(26):
			if maxa < d[i]:
				ch = chr(i + 97)
				maxa = d[i]
		if maxa > (n + 1) // 2:
			return ''
		res = [0] * n
		idx = 0
		for i in range(maxa):
			res[idx] = ch
			idx += 2
		d[ord(ch) - 97] = 0
		for i in range(26):
			while d[i] > 0:
				if idx >= n:
					idx = 1
				res[idx] = chr(i + 97)
				d[i] -= 1
				idx += 2
		return ''.join(res)


from collections import Counter
from heapq import heappush, heappop, heapify

class Solution:

	def rearrangeString(self, s):
		(tempList, result, c) = ([], '', Counter(s))
		for i in c:
			heappush(tempList, (-c[i], i))
		(newIdx, newKey) = (0, '')
		while tempList:
			(tempIdx, tempValue) = heappop(tempList)
			result += tempValue
			if newIdx < 0:
				heappush(tempList, (newIdx, newKey))
			tempIdx += 1
			(newIdx, newKey) = (tempIdx, tempValue)
		if len(result) == len(s):
			return result
		else:
			return ''


from collections import defaultdict
from heapq import heappush, heappop

class Solution:

	def rearrangeString(self, string):
		freq = defaultdict(int)
		max_heap = []
		for s in string:
			freq[s] += 1
		for (key, val) in freq.items():
			heappush(max_heap, [-val, key])
		answer = ''
		while len(max_heap) > 1:
			(f1, char1) = heappop(max_heap)
			(f2, char2) = heappop(max_heap)
			(f1, f2) = (-f1, -f2)
			answer += char1
			answer += char2
			f1 -= 1
			f2 -= 1
			if f1 != 0:
				heappush(max_heap, [-f1, char1])
			if f2 != 0:
				heappush(max_heap, [-f2, char2])
		if len(max_heap) == 1:
			(f1, char1) = heappop(max_heap)
			answer += char1
		return answer


from heapq import heappush, heappop
from collections import defaultdict

class Key:

	def __init__(self, char, freq):
		self.char = char
		self.freq = freq

	def __lt__(self, other):
		return self.freq > other.freq

class Solution:

	def rearrangeString(self, string):
		count = defaultdict(int)
		for s in string:
			count[s] += 1
		heap = []
		for (key, value) in count.items():
			heappush(heap, Key(key, value))
		ans = ''
		prev = Key('$', -1)
		while heap:
			key = heappop(heap)
			ans += key.char
			key.freq -= 1
			if prev.freq > 0:
				heappush(heap, prev)
			prev = key
		return ans


import heapq

class Solution:

	def rearrangeString(self, string):
		freq = [0] * 26
		n = len(string)
		for ele in string:
			freq[ord(ele) - 97] += 1
		pq = []
		for i in range(26):
			if freq[i] > 0:
				heapq.heappush(pq, [-freq[i], chr(i + 97)])
		if -pq[0][0] > (n + 1) // 2:
			return ''
		res = [''] * n
		idx = 0
		while pq != []:
			(count, ele) = heapq.heappop(pq)
			count *= -1
			while count > 0:
				res[idx] = ele
				idx += 2
				count -= 1
				if idx >= n:
					idx = 1
		return ''.join(res)


from heapq import heapify, heappush, heappop

class Node:

	def __init__(self, char, freq):
		self.char = char
		self.freq = freq

	def __lt__(self, other):
		return self.freq > other.freq

class Solution:

	def rearrangeString(self, s):
		heap = []
		n = len(s)
		d = {}
		for i in s:
			d[i] = d.get(i, 0) + 1
		for (k, val) in d.items():
			heappush(heap, Node(k, val))
		new_str = ''
		prev = None
		while heap:
			node = heappop(heap)
			new_str = new_str + node.char
			node.freq = node.freq - 1
			if prev and prev.freq:
				heappush(heap, prev)
			prev = node
		if len(new_str) != n:
			return -1
		return new_str


from heapq import heapify, heappush, heappop

class Solution:

	def rearrangeString(self, string):
		d = {}
		for i in string:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		heap = []
		for i in d:
			heappush(heap, (-1 * d[i], i))
		string = ''
		var = 0
		while heap:
			(a, b) = heappop(heap)
			if var != 0:
				heappush(heap, var)
			string += b
			if a + 1 != 0:
				var = (a + 1, b)
			else:
				var = 0
		if var != 0:
			(a, b) = var
			string += b * (-1 * a)
		return string


from heapq import *

class Solution:

	def rearrangeString(self, string):
		d = {}
		for c in string:
			d[c] = d.get(c, 0) + 1
		ans = ''
		li = []
		for i in d.keys():
			heappush(li, [-1 * d[i], i])
		prev = [1000000000, '#']
		while len(li) != 0:
			k = heappop(li)
			ans = ans + k[1]
			k[0] += 1
			if prev[0] < 0:
				heappush(li, prev)
			prev = k
		if len(ans) != len(string):
			return '-1'
		return ans


from math import ceil

class Solution:

	def rearrangeString(self, string):
		count = [0] * 26
		for i in string:
			count[ord(i) - ord('a')] += 1
		(maxchar, maxcharcnt) = self.getMaxCharAndIdx(count)
		if maxcharcnt > ceil(len(string) / 2):
			return string
		out = [None] * len(string)
		idx = 0
		while maxcharcnt > 0:
			out[idx] = maxchar
			maxcharcnt -= 1
			idx += 2
		count[ord(maxchar) - ord('a')] = 0
		for i in range(26):
			cur_key = chr(i + ord('a'))
			while count[i] > 0:
				if idx >= len(string):
					idx = 1
				out[idx] = cur_key
				idx += 2
				count[i] -= 1
		return ''.join(out)

	def getMaxCharAndIdx(self, count):
		maxchar = 'a'
		maxcharcnt = count[0]
		for i in range(1, len(count)):
			if count[i] > maxcharcnt:
				maxchar = chr(i + ord('a'))
				maxcharcnt = count[i]
		return (maxchar, maxcharcnt)


class Solution:

	def rearrangeString(self, string):
		alp = [0] * 26
		for i in string:
			alp[ord(i) - 97] += 1
		maxcount = 0
		maxchar = ''
		for i in range(len(alp)):
			if alp[i] > maxcount:
				maxcount = alp[i]
				maxchar = chr(i + 97)
		if maxcount > (len(string) + 1) // 2:
			return ''
		res = [None] * len(string)
		ind = 0
		while maxcount:
			res[ind] = maxchar
			ind += 2
			maxcount -= 1
		alp[ord(maxchar) - 97] = 0
		for i in range(26):
			while alp[i] > 0:
				if ind >= len(string):
					ind = 1
				res[ind] = chr(i + 97)
				ind += 2
				alp[i] -= 1
		return ''.join(res)


import heapq

class Solution:

	def rearrangeString(self, string):
		char_count = [0] * 26
		for char in string:
			index = ord(char) - ord('a')
			char_count[index] += 1
		max_heap = []
		for i in range(26):
			if char_count[i] == 0:
				continue
			heapq.heappush(max_heap, (-1 * char_count[i], chr(ord('a') + i)))
		new_str = ''
		while max_heap:
			(n_count, char) = heapq.heappop(max_heap)
			if not new_str or not max_heap or new_str[-1] != char:
				new_str += char
				n_count += 1
				if n_count < 0:
					heapq.heappush(max_heap, (n_count, char))
			else:
				(n_count2, char2) = heapq.heappop(max_heap)
				new_str += char2
				n_count2 += 1
				if n_count2 < 0:
					heapq.heappush(max_heap, (n_count2, char2))
				heapq.heappush(max_heap, (n_count, char))
		return new_str


class Solution:

	def rearrangeString(self, string):
		n = len(string)
		ordA = ord('a')
		mp = [[chr(ordA + i), 0] for i in range(26)]
		for i in string:
			mp[ord(i) - ordA][1] += 1
			if mp[ord(i) - ordA][1] > (n + 1) // 2:
				return '-1'
		mp.sort(key=lambda x: x[1], reverse=True)
		lst = ['' for i in range(n)]
		ind = 0
		first_char = mp[0][0]
		for j in range(mp[0][1]):
			lst[ind] = first_char
			ind += 2
		for i in range(1, 26):
			if mp[i][1] == 0:
				break
			else:
				val = mp[i][0]
				for i in range(mp[i][1]):
					if ind >= n:
						ind = 1
					lst[ind] = val
					ind += 2
		return lst


class Solution:

	def rearrangeString(self, string):
		out = [''] * len(string)
		tracker = {}
		for i in string:
			if i in tracker:
				tracker[i] += 1
			else:
				tracker[i] = 1
		items = list(tracker.items())
		items.sort(key=lambda x: x[1], reverse=True)
		for i in range(0, len(string), 2):
			(c, v) = items.pop(0)
			out[i] = c
			v -= 1
			if v != 0:
				items.insert(0, (c, v))
		for i in range(1, len(string), 2):
			(c, v) = items.pop(0)
			out[i] = c
			v -= 1
			if v != 0:
				items.insert(0, (c, v))
		res = ''
		for i in out:
			res += i
		return res


from collections import Counter

class Solution:

	def rearrangeString(self, string):
		s = Counter(string)
		maximum = 0
		char = 0
		for (key, value) in s.items():
			if maximum < value:
				maximum = value
				char = key
		result = [''] * len(string)
		index = 0
		s.pop(char)
		while index < len(string):
			if maximum == 0:
				break
			result[index] = char
			index += 2
			maximum -= 1
		for (char, value) in s.items():
			while value > 0:
				if index >= len(string):
					index = 1
				result[index] = char
				index += 2
				value -= 1
		return ''.join(result)


from collections import Counter

class Solution:

	def rearrangeString(self, string):
		counts = Counter(string)
		newstr = ''
		while counts:
			maxkey = max(counts, key=counts.get)
			checkkey = [i for (i, j) in counts.items() if i != maxkey and j != 0]
			if checkkey:
				newstr += maxkey + checkkey[0]
				counts[checkkey[0]] -= 1
				counts[maxkey] -= 1
			else:
				newstr += maxkey * counts[maxkey]
				counts[maxkey] = 0
			if counts[maxkey] == 0:
				counts.pop(maxkey)
		return newstr


import collections
import heapq

class Solution:

	def rearrangeString(self, string):
		counts = collections.Counter(string)
		freqs = [(-count, char) for (char, count) in counts.items()]
		heapq.heapify(freqs)
		res = ''
		prev = (0, '')
		while freqs:
			(count, char) = heapq.heappop(freqs)
			res += char
			count += 1
			if prev[0] != 0:
				heapq.heappush(freqs, prev)
			prev = (count, char)
		if prev[0] == 0:
			return res
		else:
			return 1


class Solution:

	def rearrangeString(self, string):
		n = len(string)
		if n == 1:
			return string
		count = [0] * 26
		for i in string:
			count[ord(i) - ord('a')] += 1
		maxCount = 0
		maxChar = ''
		for i in range(26):
			if count[i] > maxCount:
				maxCount = count[i]
				maxChar = chr(i + ord('a'))
		if maxCount > (n + 1) // 2:
			return string
		res = [0] * 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)


from collections import Counter

class Solution:

	def rearrangeString(self, string):
		temp = 0
		res = 0
		l = len(string)
		arr = [0] * l
		c = Counter(string)
		for i in c:
			if c[i] > temp:
				temp = c[i]
				res = i
		m = 0
		for j in range(temp):
			arr[m] = res
			m = m + 2
		for p in c:
			if p != res:
				x = c[p]
				while x > 0:
					if m >= l:
						m = 1
					arr[m] = p
					m = m + 2
					x = x - 1
		return ''.join(arr)


class Solution:

	def rearrangeString(self, string):
		chars = [0] * 26
		n = len(string)
		for i in range(n):
			chars[ord(string[i]) - ord('a')] += 1
		max_count = 0
		for i in range(26):
			if max_count < chars[i]:
				max_count = chars[i]
				max_char = chr(i + ord('a'))
		if max_count > (n + 1) / 2:
			return False
		res = [0] * n
		ind = 0
		while max_count:
			res[ind] = max_char
			ind += 2
			max_count -= 1
		chars[ord(max_char) - ord('a')] = 0
		for i in range(26):
			while chars[i]:
				if ind >= n:
					ind = 1
				res[ind] = chr(i + ord('a'))
				chars[i] -= 1
				ind += 2
		return ''.join(res)


from math import ceil

class Solution:

	def rearrangeString(self, string):
		charCount = [0] * 26
		for i in range(len(string)):
			charCount[ord(string[i]) - ord('a')] += 1
		max_key = None
		max_val = -1
		for i in range(len(charCount)):
			if charCount[i] > max_val:
				max_val = charCount[i]
				max_key = chr(i + ord('a'))
		if max_val > ceil(len(string) / 2):
			return string
		out = [None] * len(string)
		idx = 0
		while max_val:
			out[idx] = max_key
			idx += 2
			max_val -= 1
		n = len(string)
		for i in range(26):
			cur_key = chr(i + ord('a'))
			while charCount[i] > 0 and cur_key != max_key:
				if idx >= n:
					idx = 1
				out[idx] = cur_key
				idx += 2
				charCount[i] -= 1
		return ''.join(out)


from math import ceil

class Solution:

	def rearrangeString(self, string):
		charCount = [0] * 26
		for i in range(len(string)):
			charCount[ord(string[i]) - ord('a')] += 1
		maxVal = -1
		maxKey = None
		for i in range(len(charCount)):
			if maxVal < charCount[i]:
				maxVal = charCount[i]
				maxKey = chr(i + ord('a'))
		if maxVal > ceil(len(string) / 2):
			return string
		out = [None] * len(string)
		idx = 0
		while maxVal > 0:
			out[idx] = maxKey
			idx += 2
			maxVal -= 1
		n = len(string)
		for i in range(26):
			key = chr(i + ord('a'))
			while charCount[i] > 0 and key != maxKey:
				if idx >= n:
					idx = 1
				out[idx] = chr(i + ord('a'))
				idx += 2
				charCount[i] -= 1
		return ''.join(out)


from math import ceil

class Solution:

	def maxCompute(self, arr):
		max_count = 0
		maxchar = ''
		for i in range(26):
			if arr[i] > max_count:
				max_count = arr[i]
				max_char = i
		return (chr(max_char + ord('a')), max_count)

	def rearrangeString(self, string):
		count = [0] * 26
		for i in range(len(string)):
			count[ord(string[i]) - ord('a')] += 1
		(maxchar, maxcount) = self.maxCompute(count)
		if maxcount > ceil(len(string) / 2):
			return string
		out = [None] * len(string)
		index = 0
		while maxcount:
			out[index] = maxchar
			index += 2
			maxcount -= 1
		count[ord(maxchar) - ord('a')] = 0
		n = len(string)
		for i in range(26):
			while count[i] > 0:
				if index >= n:
					index = 1
				out[index] = chr(i + ord('a'))
				index += 2
				count[i] -= 1
		return ''.join(out)