Leetcode 2785: Sort Vowels in a String
You are given a string s. The task is to permute s such that all consonants remain in their original places, and the vowels are sorted in the nondecreasing order of their ASCII values.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s containing only English letters (uppercase and lowercase).
Example: Input: s = 'ReAcTivE'
Constraints:
• 1 <= s.length <= 10^5
• s consists only of letters of the English alphabet in uppercase and lowercase.
Output: Return the new string where the consonants remain in their original places and the vowels are sorted in non-decreasing ASCII order.
Example: Output: 'ReACTivE'
Constraints:
Goal: Sort the vowels in the string while leaving consonants in place.
Steps:
• Extract the vowels from the string and store them in a list.
• Sort the list of vowels based on their ASCII values.
• Reconstruct the string by replacing the vowels in their original positions with the sorted vowels.
Goal: Constraints on the input size and string content.
Steps:
• 1 <= s.length <= 10^5
• s consists only of English alphabet letters (uppercase and lowercase).
Assumptions:
• The input string may contain both uppercase and lowercase vowels.
• Input: Input: 'ReAcTivE'
• Explanation: The vowels in 'ReAcTivE' are 'e', 'A', 'i'. After sorting them based on their ASCII values, the new string becomes 'ReACTivE'.
• Input: Input: 'hEllOWoRlD'
• Explanation: The vowels 'e', 'O', 'O' are sorted, resulting in 'hElLOOWrLD'.
Approach: Extract the vowels, sort them, and reinsert them into the original string in place of the vowels.
Observations:
• Only the vowels need to be rearranged. Consonants stay in their places.
• Sorting the vowels based on their ASCII values is straightforward.
• I will extract vowels, sort them, and replace them in the original positions.
Steps:
• Identify the positions of vowels in the string.
• Extract the vowels and sort them.
• Rebuild the string by replacing the original vowels with the sorted ones.
Empty Inputs:
• Input: ''. Output: ''
Large Inputs:
• Input: 'a' repeated 10^5 times. Output: 'a' repeated 10^5 times.
Special Values:
• Input: 'bCdfgh' (no vowels). Output: 'bCdfgh'.
Constraints:
• The solution should handle up to 10^5 characters efficiently.
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'o'|| ch == 'u'|| ch == 'i';
}
string sortVowels(string s) {
string v;
copy_if(begin(s), end(s), back_inserter(v), [&](char ch){
return isVowel(tolower(ch));
});
sort(begin(v), end(v));
for (int i = 0, j = 0; i < s.size(); ++i)
if (isVowel(tolower(s[i])))
s[i] = v[j++];
return s;
}
1 : Function Declaration
bool isVowel(char ch) {
This function `isVowel` takes a character `ch` as input and checks if it is one of the vowels ('a', 'e', 'o', 'u', 'i'). It returns true if the character is a vowel, and false otherwise.
2 : Vowel Check
return ch == 'a' || ch == 'e' || ch == 'o'|| ch == 'u'|| ch == 'i';
This line compares the input character `ch` against the five vowels ('a', 'e', 'o', 'u', 'i') and returns true if the character matches any of them.
3 : Function Declaration
string sortVowels(string s) {
This function `sortVowels` takes a string `s` as input and returns a new string with the vowels sorted in ascending order, while keeping the consonants in their original positions.
4 : Variable Initialization
string v;
A string `v` is initialized to hold all the vowels extracted from the input string `s`.
5 : Copying Vowels
copy_if(begin(s), end(s), back_inserter(v), [&](char ch){
The `copy_if` function iterates over the string `s` and copies each character that is a vowel (determined by the `isVowel` function) into the string `v`.
6 : Vowel Check
return isVowel(tolower(ch));
This lambda function checks if the character `ch` (converted to lowercase using `tolower`) is a vowel by calling the `isVowel` function.
7 : Sorting Vowels
sort(begin(v), end(v));
This line sorts the string `v` in ascending order so that the vowels are arranged alphabetically.
8 : Looping Through String
for (int i = 0, j = 0; i < s.size(); ++i)
This for loop iterates through each character of the string `s`. The variable `i` is the index for the original string, and `j` is used to track the position in the sorted `v` string.
9 : Vowel Replacement
if (isVowel(tolower(s[i])))
This condition checks if the current character in the string `s` (converted to lowercase) is a vowel.
10 : Replacing Character
s[i] = v[j++];
If the character is a vowel, it is replaced by the next vowel in the sorted string `v`, and the index `j` is incremented.
11 : Returning Result
return s;
After all vowels are replaced with the sorted vowels, the modified string `s` is returned.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The most time-consuming operation is sorting the vowels, which takes O(n log n) time.
Best Case: O(n)
Worst Case: O(n)
Description: We store the vowels and need extra space proportional to the size of the string.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus