Given a sorted string S consisting of N lowercase characters, the task is to rearrange characters in the given string such that no two adjacent characters are the same. If it is not possible to rearrange as per the given criteria, then print “-1”.
Examples:
Input: S = “aaabc”
Output: abacaInput: S = “aa”
Output: -1
Approach: The given problem can be solved by using the Two-Pointer Technique. Follow the steps below to solve this problem:
- Iterate over the characters of the string S and check if no two adjacent characters are the same in the string then print the string S.
- Otherwise, if the size of the string is 2 and has the same characters, then print “-1”.
- Initialize three variables, say, i as 0, j as 1, and k as 2 to traverse over the string S.
- Iterate while k is less than N and perform the following steps:
- If S[i] is not equal to S[j], then increment i and j by 1, and increment k by 1, if the value of j is equal to k.
- Else if S[j] equals S[k], increment k by 1.
- Else, swap s[j] and s[k] and increment i and j by 1, and if j is equal to k, then increment k by 1.
- After completing the above steps reverse the string S.
- Finally, iterate over the characters of the string S and check if no two adjacent characters are the same. If found to be true then print string S. Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a string S // contains pair of adjacent // characters that are equal or not bool isAdjChar(string& s) { // Traverse the string S for ( int i = 0; i < s.size() - 1; i++) { // If S[i] and S[i+1] are equal if (s[i] == s[i + 1]) return true ; } // Otherwise, return false return false ; } // Function to rearrange characters // of a string such that no pair of // adjacent characters are the same void rearrangeStringUtil(string& S, int N) { // Initialize 3 variables int i = 0, j = 1, k = 2; // Iterate until k < N while (k < N) { // If S[i] is not equal // to S[j] if (S[i] != S[j]) { // Increment i and j by 1 i++; j++; // If j equals k and increment // the value of K by 1 if (j == k) { k++; } } // Else else { // If S[j] equals S[k] if (S[j] == S[k]) { // Increment k by 1 k++; } // Else else { // Swap swap(S[k], S[j]); // Increment i and j // by 1 i++; j++; // If j equals k if (j == k) { // Increment k by 1 k++; } } } } } // Function to rearrange characters // in a string so that no two // adjacent characters are same string rearrangeString(string& S, int N) { // If string is already valid if (isAdjChar(S) == false ) { return S; } // If size of the string is 2 if (S.size() == 2) return "-1" ; // Function Call rearrangeStringUtil(S, N); // Reversing the string reverse(S.begin(), S.end()); // Function Call rearrangeStringUtil(S, N); // If the string is valid if (isAdjChar(S) == false ) { return S; } // Otherwise return "-1" ; } // Driver Code int main() { string S = "aaabc" ; int N = S.length(); cout << rearrangeString(S, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static char []S = "aaabc" .toCharArray(); // Function to check if a String S // contains pair of adjacent // characters that are equal or not static boolean isAdjChar() { // Traverse the String S for ( int i = 0 ; i < S.length - 1 ; i++) { // If S[i] and S[i+1] are equal if (S[i] == S[i + 1 ]) return true ; } // Otherwise, return false return false ; } // Function to rearrange characters // of a String such that no pair of // adjacent characters are the same static void rearrangeStringUtil( int N) { // Initialize 3 variables int i = 0 , j = 1 , k = 2 ; // Iterate until k < N while (k < N) { // If S[i] is not equal // to S[j] if (S[i] != S[j]) { // Increment i and j by 1 i++; j++; // If j equals k and increment // the value of K by 1 if (j == k) { k++; } } // Else else { // If S[j] equals S[k] if (S[j] == S[k]) { // Increment k by 1 k++; } // Else else { // Swap swap(k,j); // Increment i and j // by 1 i++; j++; // If j equals k if (j == k) { // Increment k by 1 k++; } } } } } static void swap( int i, int j) { char temp = S[i]; S[i] = S[j]; S[j] = temp; } // Function to rearrange characters // in a String so that no two // adjacent characters are same static String rearrangeString( int N) { // If String is already valid if (isAdjChar() == false ) { return String.valueOf(S); } // If size of the String is 2 if (S.length == 2 ) return "-1" ; // Function Call rearrangeStringUtil(N); // Reversing the String reverse(); // Function Call rearrangeStringUtil(N); // If the String is valid if (isAdjChar() == false ) { return String.valueOf(S); } // Otherwise return "-1" ; } static void reverse() { int l, r = S.length - 1 ; for (l = 0 ; l < r; l++, r--) { char temp = S[l]; S[l] = S[r]; S[r] = temp; } } // Driver Code public static void main(String[] args) { int N = S.length; System.out.print(rearrangeString(N)); } } // This code is contributed by Princi Singh |
Python3
# Python 3 program for the above approach S = "aaabc" # Function to check if a string S # contains pair of adjacent # characters that are equal or not def isAdjChar(s): # Traverse the string S for i in range ( len (s) - 1 ): # If S[i] and S[i+1] are equal if (s[i] = = s[i + 1 ]): return True # Otherwise, return false return False # Function to rearrange characters # of a string such that no pair of # adjacent characters are the same def rearrangeStringUtil(N): global S S = list (S) # Initialize 3 variables i = 0 j = 1 k = 2 # Iterate until k < N while (k < N): # If S[i] is not equal # to S[j] if (S[i] ! = S[j]): # Increment i and j by 1 i + = 1 j + = 1 # If j equals k and increment # the value of K by 1 if (j = = k): k + = 1 # Else else : # If S[j] equals S[k] if (S[j] = = S[k]): # Increment k by 1 k + = 1 # Else else : # Swap temp = S[k] S[k] = S[j] S[j] = temp # Increment i and j # by 1 i + = 1 j + = 1 # If j equals k if (j = = k): # Increment k by 1 k + = 1 S = ''.join(S) # Function to rearrange characters # in a string so that no two # adjacent characters are same def rearrangeString(N): global S # If string is already valid if (isAdjChar(S) = = False ): return S # If size of the string is 2 if ( len (S) = = 2 ): return "-1" # Function Call rearrangeStringUtil(N) # Reversing the string S = S[:: - 1 ] # Function Call rearrangeStringUtil(N) # If the string is valid if (isAdjChar(S) = = False ): return S # Otherwise return "-1" # Driver Code if __name__ = = '__main__' : N = len (S) print (rearrangeString(N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; public class GFG { static char []S = "aaabc" .ToCharArray(); // Function to check if a String S // contains pair of adjacent // characters that are equal or not static bool isAdjChar() { // Traverse the String S for ( int i = 0; i < S.Length - 1; i++) { // If S[i] and S[i+1] are equal if (S[i] == S[i + 1]) return true ; } // Otherwise, return false return false ; } // Function to rearrange characters // of a String such that no pair of // adjacent characters are the same static void rearrangeStringUtil( int N) { // Initialize 3 variables int i = 0, j = 1, k = 2; // Iterate until k < N while (k < N) { // If S[i] is not equal // to S[j] if (S[i] != S[j]) { // Increment i and j by 1 i++; j++; // If j equals k and increment // the value of K by 1 if (j == k) { k++; } } // Else else { // If S[j] equals S[k] if (S[j] == S[k]) { // Increment k by 1 k++; } // Else else { // Swap swap(k,j); // Increment i and j // by 1 i++; j++; // If j equals k if (j == k) { // Increment k by 1 k++; } } } } } static void swap( int i, int j) { char temp = S[i]; S[i] = S[j]; S[j] = temp; } // Function to rearrange characters // in a String so that no two // adjacent characters are same static String rearrangeString( int N) { // If String is already valid if (isAdjChar() == false ) { return String.Join( "" ,S); } // If size of the String is 2 if (S.Length == 2) return "-1" ; // Function Call rearrangeStringUtil(N); // Reversing the String reverse(); // Function Call rearrangeStringUtil(N); // If the String is valid if (isAdjChar() == false ) { return String.Join( "" ,S); } // Otherwise return "-1" ; } static void reverse() { int l, r = S.Length - 1; for (l = 0; l < r; l++, r--) { char temp = S[l]; S[l] = S[r]; S[r] = temp; } } // Driver Code public static void Main(String[] args) { int N = S.Length; Console.Write(rearrangeString(N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach let S = "aaabc" // Function to check if a string S // contains pair of adjacent // characters that are equal or not function isAdjChar(s){ // Traverse the string S for (let i = 0; i < s.length - 1; i++){ // If S[i] and S[i+1] are equal if (s[i] == s[i + 1]) return true } // Otherwise, return false return false } // Function to rearrange characters // of a string such that no pair of // adjacent characters are the same function rearrangeStringUtil(N){ S = S.split( "" ) // Initialize 3 variables let i = 0 let j = 1 let k = 2 // Iterate until k < N while (k < N){ // If S[i] is not equal // to S[j] if (S[i] != S[j]){ // Increment i and j by 1 i += 1 j += 1 // If j equals k and increment // the value of K by 1 if (j == k) k += 1 } // Else else { // If S[j] equals S[k] if (S[j] == S[k]){ // Increment k by 1 k += 1 } // Else else { // Swap let temp = S[k] S[k] = S[j] S[j] = temp // Increment i and j // by 1 i += 1 j += 1 // If j equals k if (j == k){ // Increment k by 1 k += 1 } } } } S = S.join( '' ) } // Function to rearrange characters // in a string so that no two // adjacent characters are same function rearrangeString(N){ // If string is already valid if (isAdjChar(S) == false ) return S // If size of the string is 2 if (S.length == 2) return "-1" // Function Call rearrangeStringUtil(N) // Reversing the string S = S.split( "" ).reverse().join( "" ) // Function Call rearrangeStringUtil(N) // If the string is valid if (isAdjChar(S) == false ) return S // Otherwise return "-1" } // Driver Code let N = S.length; document.write(rearrangeString(N)) // This code is contributed by shinjanpatra </script> |
acaba
Time Complexity: O(N), as we are using reverse function which will cost O (N) time.
Auxiliary Space: O(1), as we are not using any extra space.
Another Approach:
The above approach has a time complexity of O(N) due to the nested while loop used in the rearrangeStringUtil function. Here’s a more efficient approach with a time complexity of O(N log N):
Approach: This code takes a string as input and rearranges its characters such that no two adjacent characters are the same. If such a rearrangement is not possible, it returns “-1”.
The approach of the code is as follows:
- Create a frequency map of characters in the input string using a HashMap. The key of the map is a character and the value is its frequency in the string
- Create a max heap using a PriorityQueue to store the character-frequency pairs. The max heap is sorted based on the frequency of characters, such that the character with the highest frequency is at the top of the heap.
- While the max heap is not empty, poll the two characters with the highest frequency from the heap.
- If the frequency of the second character is not zero, append both characters to the result string and decrement their frequency in the frequency map.
- Add the characters back to the max heap if their frequency is greater than zero.
- If the heap is empty and the frequency of the first character is greater than one, return “-1”.
- If the heap is empty and the frequency of the first character is one, append it to the result string.
- Return the result string.
Below is the implementation of the above approach:
Java
import java.util.*; public class Main { public static String rearrangeString(String s) { // Create character frequency map Map<Character, Integer> freqMap = new HashMap<>(); for ( char c : s.toCharArray()) { freqMap.put(c, freqMap.getOrDefault(c, 0 ) + 1 ); } // Use max heap to store characters by frequency PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>( (a, b) -> b.getValue() - a.getValue()); maxHeap.addAll(freqMap.entrySet()); // Initialize result string StringBuilder res = new StringBuilder(); // Repeat while heap is not empty while (!maxHeap.isEmpty()) { // Poll most frequent character Map.Entry<Character, Integer> entry1 = maxHeap.poll(); char ch1 = entry1.getKey(); int freq1 = entry1.getValue(); // Poll next most frequent character Map.Entry<Character, Integer> entry2 = maxHeap.poll(); if (entry2 != null ) { char ch2 = entry2.getKey(); int freq2 = entry2.getValue(); // Append to result string res.append(ch1); res.append(ch2); // Decrement frequency in map freqMap.put(ch1, freqMap.get(ch1) - 1 ); freqMap.put(ch2, freqMap.get(ch2) - 1 ); // Add back to heap if frequency is greater than 0 if (freqMap.get(ch1) > 0 ) { maxHeap.offer( new AbstractMap.SimpleEntry<>(ch1, freqMap.get(ch1))); } if (freqMap.get(ch2) > 0 ) { maxHeap.offer( new AbstractMap.SimpleEntry<>(ch2, freqMap.get(ch2))); } } // If heap is empty but frequency of current character is greater than 1 else if (freq1 > 1 ) { return "-1" ; } // Append last character if heap is empty and frequency is 1 else { res.append(ch1); } } // Return result string return res.toString(); } public static void main(String[] args) { String s = "aaabc" ; System.out.println(rearrangeString(s)); } } //This code is contributed by rudra1807raj |
Python3
import heapq from collections import defaultdict def rearrangeString(s): # Create character frequency map freqMap = defaultdict( int ) for c in s: freqMap + = 1 # Use max heap to store characters by frequency maxHeap = [( - freq, char) for char, freq in freqMap.items()] heapq.heapify(maxHeap) # Initialize result string res = [] # Repeat while heap is not empty while maxHeap: # Pop most frequent character freq1, ch1 = heapq.heappop(maxHeap) # Pop next most frequent character if maxHeap: freq2, ch2 = heapq.heappop(maxHeap) # Append to result string res.extend([ch1, ch2]) # Decrement frequency in map freqMap[ch1] - = 1 freqMap[ch2] - = 1 # Add back to heap if frequency is greater than 0 if freqMap[ch1] > 0 : heapq.heappush(maxHeap, ( - freqMap[ch1], ch1)) if freqMap[ch2] > 0 : heapq.heappush(maxHeap, ( - freqMap[ch2], ch2)) # If heap is empty but frequency of current character is greater than 1 elif freq1 < - 1 : return "-1" # Append last character if heap is empty and frequency is 1 else : res.append(ch1) # Return result string return "".join(res) s = "aaabc" print (rearrangeString(s)) #This code is contributed by rudra1807raj |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; string rearrangeString(string s) { // Create character frequency map unordered_map< char , int > freqMap; for ( char c : s) { freqMap++; } // Use max heap to store characters // by frequency priority_queue<pair< int , char > > maxHeap; for ( auto & entry : freqMap) { maxHeap.push(make_pair(entry.second, entry.first)); } // Initialize result string string res = "" ; // Repeat while heap is not empty while (!maxHeap.empty()) { // Poll most frequent character auto entry1 = maxHeap.top(); maxHeap.pop(); char ch1 = entry1.second; int freq1 = entry1.first; // Poll next most frequent character char ch2 = '\0' ; int freq2 = 0; if (!maxHeap.empty()) { auto entry2 = maxHeap.top(); maxHeap.pop(); ch2 = entry2.second; freq2 = entry2.first; } // Append to result string res += ch1; if (ch2 != '\0' ) { res += ch2; } // Decrement frequency in map freqMap[ch1]--; freqMap[ch2]--; // Add back to heap if frequency // is greater than 0 if (freqMap[ch1] > 0) { maxHeap.push(make_pair(freqMap[ch1], ch1)); } if (freqMap[ch2] > 0) { maxHeap.push(make_pair(freqMap[ch2], ch2)); } } // Check if result string is valid for ( int i = 1; i < res.length(); i++) { if (res[i] == res[i - 1]) { return "-1" ; } } // Return result string return res; } // Driver Code int main() { string s = "aaabc" ; cout << rearrangeString(s); return 0; } |
acaba
Time Complexity: The time complexity of this approach is O(n log n), where n is the length of the input string. This is because the code involves iterating over the characters of the input string, creating a frequency map of the characters, creating a max heap, and while the heap is not empty, polling the two characters with the highest frequency from the heap and appending them to the result string. Each operation takes O(log n) time, and since each character is processed once, the overall time complexity is O(n log n).
Auxiliary Space: The space complexity of this approach is also O(n), where n is the length of the input string. This is because the code involves creating a frequency map of the characters, a max heap, and a result string. The size of the frequency map and the max heap is at most the number of distinct characters in the input string, which is O(n) in the worst case. The size of the result string is also O(n) in the worst case since it contains all the characters of the input string. Therefore, the overall space complexity is O(n).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!