Python: Check if the letters of a given string can be rearranged so that two characters that are adjacent to each other are different
Python heap queue algorithm: Exercise-15 with Solution
Write a Python program to check if the letters in a given string can be rearranged. This is to make sure that two characters that are adjacent to each other are different using the heap queue algorithm.
If there is no output return the empty string.
import heapq from collections import Counter def reorganizeString(S): ctr = Counter(S) heap = [(-value, key) for key, value in ctr.items()] heapq.heapify(heap) if (-heap) * 2 > len(S) + 1: return "" ans =  while len(heap) >= 2: nct1, char1 = heapq.heappop(heap) nct2, char2 = heapq.heappop(heap) ans.extend([char1, char2]) if nct1 + 1: heapq.heappush(heap, (nct1 + 1, char1)) if nct2 + 1: heapq.heappush(heap, (nct2 + 1, char2)) return "".join(ans) + (heap if heap else "") print(reorganizeString("aab")) print(reorganizeString("abc")) print(reorganizeString("aabb")) print(reorganizeString("abccdd"))
aba abc abab cdabcd
Python Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
Previous: Write a Python program to get the k most frequent elements from a given non-empty list of words using Heap queue algorithm.
Next: Write a Python program which add integer numbers from the data stream to a heapq and compute the median of all elements.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends
- Python Interview Questions and Answers: Comprehensive Guide
- Scala Exercises, Practice, Solution
- Kotlin Exercises practice with solution
- MongoDB Exercises, Practice, Solution
- SQL Exercises, Practice, Solution - JOINS
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join