Given a string str, the task is to rearrange the characters of the given string such that the minimum distance between any pair of vowels is maximum possible.
Examples:
Input: str = “aacbbc”
Output: abcbca
Explanation: Maximized distance between the only pair of vowels is 4.Input: str = “aaaabbbcc”
Output: ababacbac
Approach: Follow the below steps to solve the problem:
- Iterate over the characters of the string and count the number of vowels and consonants present in the string str, say Nv and Nc respectively.
- Now, calculate the maximum number of consonants that can be put between every pair of vowels using the following formula:
M = rounded down[Nc / (Nv – 1)]
- Now, construct the resultant string by placing all vowels and then inserting M consonants between each adjacent vowel of the pair.
- After constructing the resultant string, if any consonant is still remaining, then simply insert them at the end of the string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the string// such that the minimum distance// between any of vowels is maximum.string solution(string s){ // Store vowels and consonants vector<char> vowel, consonant; // Iterate over the characters // of string for (auto i : s) { // If current character is a vowel if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') { vowel.push_back(i); } // If current character is // a consonant else { consonant.push_back(i); } } // Stores count of vowels and // consonants respectively int Nc, Nv; Nv = vowel.size(); Nc = consonant.size(); int M = Nc / (Nv - 1); // Stores the resultant string string ans = ""; // Stores count of consonants // appended into ans int consotnant_till = 0; for (auto i : vowel) { // Append vowel to ans ans += i; int temp = 0; // Append consonants for (int j = consotnant_till; j < min(Nc, consotnant_till + M); j++) { // Append consonant to ans ans += consonant[j]; // Update temp temp++; } // Remove the taken // elements of consonant consotnant_till += temp; } // Return final ans return ans;}// Driver Codeint main(){ string str = "aaaabbbcc"; // Function Call cout << solution(str); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to rearrange the String// such that the minimum distance// between any of vowels is maximum.static String solution(String s){ // Store vowels and consonants Vector<Character> vowel = new Vector<Character>(); Vector<Character> consonant = new Vector<Character>(); // Iterate over the characters // of String for (char i : s.toCharArray()) { // If current character is a vowel if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') { vowel.add(i); } // If current character is // a consonant else { consonant.add(i); } } // Stores count of vowels and // consonants respectively int Nc, Nv; Nv = vowel.size(); Nc = consonant.size(); int M = Nc / (Nv - 1); // Stores the resultant String String ans = ""; // Stores count of consonants // appended into ans int consotnant_till = 0; for (char i : vowel) { // Append vowel to ans ans += i; int temp = 0; // Append consonants for (int j = consotnant_till; j < Math.min(Nc, consotnant_till + M); j++) { // Append consonant to ans ans += consonant.get(j); // Update temp temp++; } // Remove the taken // elements of consonant consotnant_till += temp; } // Return final ans return ans;}// Driver Codepublic static void main(String[] args){ String str = "aaaabbbcc"; // Function Call System.out.print(solution(str));}}// This code is contributed by 29AjayKumar |
Python3
# Python Program for the above approach# Function to rearrange the string # such that the minimum distance # between any of vowels is maximum. def solution(S): # store vowels and consonants vowels = [] consonants = [] # Iterate over the # characters of string for i in S: # if current character is a vowel if (i == 'a' or i == 'e' or i == 'i' or i == 'o' or i == 'u'): vowels.append(i) # if current character is consonant else: consonants.append(i) # store count of vowels and # consonants respectively Nc = len(consonants) Nv = len(vowels) M = Nc // (Nv - 1) # store the resultant string ans = "" # store count of consonants # append into ans consonant_till = 0 for i in vowels: # Append vowel to ans ans += i temp = 0 # Append consonants for j in range(consonant_till, min(Nc, consonant_till + M)): # Appendconsonant to ans ans += consonants[j] # update temp temp += 1 # Remove the taken # elements of consonant consonant_till += temp # return final answer return ans# Driver codeS = "aaaabbbcc"print(solution(S))# This code is contributed by Virusbuddah |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to rearrange the String// such that the minimum distance// between any of vowels is maximum.static String solution(string s){ // Store vowels and consonants List<char> vowel = new List<char>(); List<char> consonant = new List<char>(); // Iterate over the characters // of String foreach (char i in s.ToCharArray()) { // If current character is a vowel if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') { vowel.Add(i); } // If current character is // a consonant else { consonant.Add(i); } } // Stores count of vowels and // consonants respectively int Nc, Nv; Nv = vowel.Count; Nc = consonant.Count; int M = Nc / (Nv - 1); // Stores the resultant String string ans = ""; // Stores count of consonants // appended into ans int consotnant_till = 0; foreach (char i in vowel) { // Append vowel to ans ans += i; int temp = 0; // Append consonants for (int j = consotnant_till; j < Math.Min(Nc, consotnant_till + M); j++) { // Append consonant to ans ans += consonant[j]; // Update temp temp++; } // Remove the taken // elements of consonant consotnant_till += temp; } // Return final ans return ans;}// Driver Codestatic public void Main(){ String str = "aaaabbbcc"; // Function Call Console.WriteLine(solution(str)); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program for the above approach// Function to rearrange the string// such that the minimum distance// between any of vowels is maximum.function solution(s){ // Store vowels and consonants var vowel = [], consonant = []; // Iterate over the characters // of string s.split('').forEach(i => { // If current character is a vowel if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') { vowel.push(i); } // If current character is // a consonant else { consonant.push(i); } }); // Stores count of vowels and // consonants respectively var Nc, Nv; Nv = vowel.length; Nc = consonant.length; var M = parseInt(Nc / (Nv - 1)); // Stores the resultant string var ans = ""; // Stores count of consonants // appended into ans var consotnant_till = 0; vowel.forEach(i => { // Append vowel to ans ans += i; var temp = 0; // Append consonants for (var j = consotnant_till; j < Math.min(Nc, consotnant_till + M); j++) { // Append consonant to ans ans += consonant[j]; // Update temp temp++; } // Remove the taken // elements of consonant consotnant_till += temp; }); // Return final ans return ans;}// Driver Codevar str = "aaaabbbcc";// Function Calldocument.write( solution(str));</script> |
Output:
abababac
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
