Sort a string without altering the position of vowels

Sorting a string means we have to arrange a given string either in an ascending or descending order or any given order. In this problem given a string 'str' of size n. Our aim is to sort the given string without altering means without changing the position of vowels present in the string.

Let's see examples with explanations below to understand the problem in a better way.

Sample Examples

Input 1

str = “abdecokfee”

Output 1

abcedofkee

Explanation

Constant present in the string = bdckf

Sort the constant string = bcdfk

Merge the given string with the sorted instant string without changing the positions of vowel = abcedofkee

Input 2

str =  str = “hellothere” 

Output 2

str = hehlolrete

Explanation

Constant present in the string = hllthr

Sort the constant string = hhllrt

Merge the given string with the sorted instant string without changing the positions of vowel = hehlolrete

Approach 1: Naive Approach

The idea is simple, first store all the constants of the given string into the variable string 'temp' and sort this temp string using the sort function. In the end, replace the sorted constant string char with the given string constant char without changing the position of the vowel of the given string.

Example

Let's see the code below for a better understanding of the above approach. Below is a C++ program for sorting the string without changing the position of vowels.

#include <bits/stdc++.h>
using namespace std;
// Created a function to sort the constant char of the string 
string sortString(string str, int n){      
   string temp = ""; // Stroing the constant string    
   // Traverse the string using for loop to get constant
   for( int i=0; i<n; i++ ){
      // IF char is not vowel add to char the string temp
      if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
         temp += str[i];
      }
   }    
   // If temp string has character
   if(temp.size()){
      // Sort the constant string using sort function
      sort( temp.begin(), temp.end() );
   }    
   int idx = 0; // to traverse the constant sorting sring
   // Traverse the string using for loop to get resultant
   for( int i=0; i<n; i++ ){
      // IF char is not vowel add to char the string temp
      if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
         // Replace sorted constant with given string constant
         str[i] = temp[idx]; 
         idx++; // Increment the pointer of the sorted constant string
      }
   }
   // Return the resultant
   return str;
}
int main(){
   string S = "abdecokfee"; // Given string
   int N = S.size(); // Gettig the size of the string
   // Call the function
   string result = sortString(S, N); // Store the sorted string     
   // Print the string
   cout << "The sorted string without changing the position of the vowel is " << result;
   return 0;
}

Output

The sorted string without changing the position of the vowel is abcedofkee

Time and Space Complexity

The time complexity of the above code is O(N*(logN)), as we are using a sorting function to sort the constant string.

The space complexity of the above code is O(N), as we are storing the constant character in the new spring temp.

Where N is the size of the string.

Approach 2

In the above code, we are using a new string to store the constant character of a given string and also using the sort function to sort them but in the place of doing that we can use the map of constant size 26 and it will also store the character in the sorting manner.

Example

Below is a C++ program for sorting the string without changing the position of vowels.

#include <bits/stdc++.h>
using namespace std; 
// Function to sort the constant char of the string 
string sortString(string str, int n){
   map<char, int>mp; // Stroing the constant of the string    
   // Traverse the string using for loop to get constant
   for( int i=0; i<n; i++ ){
      // IF char is not vowel add to char the string temp
      if( str[i] != 'e' && str[i] != 'o' && str[i] != 'a' && str[i] != 'u' && str[i] != 'i' ){
         mp[ str[i] ]++;
      }
   }    
   // Check whether constant is present or not
   if(mp.size() <= 1) return str;    
   int idx = 0; // to traverse the given string    
   // Traverse the map 
   for( auto &x : mp){
      // While the current char exist
      while(x.second){
         while( str[idx] == 'e' || str[idx] == 'u' || str[idx] == 'a' || str[idx] == 'i' || str[idx] == 'o' ){
            idx++; // Increment the pointer of a given string
         }
         // Replace sorted constant with given string constant
         str[idx] = x.first;
         idx++; // Increment the pointer of a given string
         x.second--; // Decrement the current char
      }
   }
   // Return the resultant
   return str;
}
// Driver Code
int main(){
   string S = "abdecokfee"; // Given string
   int N = S.size(); // Gettig the size of the string    
   // Call the function
   string result = sortString(S, N); // Store the sorted string     
   // Print the string
   cout << "The sorted string without changing the position of the vowel is " << result;
   return 0;
}

Output

The sorted string without changing the position of the vowel is abcedofkee

Time and Space Complexity

The time complexity: O(N*(logN)). As we traverse the map.

The space complexity: O(1), as the size of the map is constant 26.

Where N is the size of the string.

Conclusion

In this tutorial, we have implemented a program to find the Sort of string without altering the position of vowels. We have implemented two approaches naive approach using the sort function and the efficient approach using a hashmap. The time complexity is O(N*(logN)) for both the approaches and the space complexity of O(N) and O(1) respectively. Where N is the size of the string.