![Data Structures & Algorithms Tutorial](https://www.tutorialspoint.com/data_structures_algorithms/images/data-structure-mini-logo.jpg)
- Data Structures & Algorithms
- DSA - Home
- DSA - Overview
- DSA - Environment Setup
- Algorithm
- DSA - Algorithms Basics
- DSA - Asymptotic Analysis
- DSA - Greedy Algorithms
- DSA - Divide and Conquer
- DSA - Dynamic Programming
- Data Structures
- DSA - Data Structure Basics
- DSA - Data Structures and Types
- DSA - Array Data Structure
- Linked Lists
- DSA - Linked List Basics
- DSA - Doubly Linked List
- DSA - Circular Linked List
- Stack & Queue
- DSA - Stack
- DSA - Expression Parsing
- DSA - Queue
- Searching Techniques
- DSA - Linear Search
- DSA - Binary Search
- DSA - Interpolation Search
- DSA - Hash Table
- Sorting Techniques
- DSA - Sorting Algorithms
- DSA - Bubble Sort
- DSA - Insertion Sort
- DSA - Selection Sort
- DSA - Merge Sort
- DSA - Shell Sort
- DSA - Quick Sort
- Graph Data Structure
- DSA - Graph Data Structure
- DSA - Depth First Traversal
- DSA - Breadth First Traversal
- Tree Data Structure
- DSA - Tree Data Structure
- DSA - Tree Traversal
- DSA - Binary Search Tree
- DSA - AVL Tree
- DSA - Red Black Trees
- DSA - B Trees
- DSA - B+ Trees
- DSA - Splay Trees
- DSA - Spanning Tree
- DSA - Tries
- DSA - Heap
- Recursion
- DSA - Recursion Basics
- DSA - Tower of Hanoi
- DSA - Fibonacci Series
- DSA Useful Resources
- DSA - Questions and Answers
- DSA - Quick Guide
- DSA - Useful Resources
- DSA - Discussion
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.
- Related Articles
- Reverse Vowels of a String in Python
- Reverse Vowels of a string in C++
- Reversing vowels in a string JavaScript
- How can we sort a string without using predefined methods in Java?
- Counting number of vowels in a string with JavaScript
- Remove Vowels from a String in Python
- Remove vowels from a String in C++
- Return Vowels in a string in JavaScript
- How to Count the Number of Vowels in a string using Python?
- C# Program to count vowels in a string
- Java Program to count vowels in a string
- First X vowels from a string in C++
- Moving all vowels to the end of string using JavaScript
- Count the pairs of vowels in the given string in C++
- Rearrange a string to maximize the minimum distance between any pair of vowels
![Tutorials Point](https://www.tutorialspoint.com/articles/images/tp-print-page-logo.png)