Scale Engineer

Sort Vowels in a String

Med
#2497Time: O(N + k log k), where N is the length of the string and k is the number of vowels. The first loop to collect vowels takes O(N) time. Sorting the list of k vowels takes O(k log k) time. The second loop to place the sorted vowels takes O(N) time. In the worst case, where all characters are vowels (k ≈ N), the complexity is O(N log N).Space: O(N), where N is the length of the string. We use a list to store the k vowels, which takes O(k) space (where k is the number of vowels). We also use a character array to build the result string, which takes O(N) space. Therefore, the total space complexity is O(k + N), which simplifies to O(N).
Algorithms
Sorting
Data structures
String

Prompt

Given a 0-indexed string s, permute s to get a new string t such that:

  • All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
  • The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

 

Example 1:

Input: s = "lEetcOde"
Output: "lEOtcede"
Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:

Input: s = "lYmpH"
Output: "lYmpH"
Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of letters of the English alphabet in uppercase and lowercase.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two main passes over the string's data. In the first pass, we identify and collect all the vowels into a separate list. In the second pass, after sorting this list of vowels, we iterate through the original string's positions again and replace the vowel positions with the sorted vowels.

Algorithm

  • Create a helper function isVowel(char c) to check if a character is a vowel.
  • Initialize an empty list, vowels, to store characters.
  • Iterate through the input string s. If a character c is a vowel, add it to the vowels list.
  • Sort the vowels list. In Java, Collections.sort() can be used, which has a time complexity of O(k log k) where k is the number of vowels.
  • Convert the input string s to a character array, resultChars.
  • Initialize an index vowelIndex = 0 to point to the current vowel in the sorted list.
  • Iterate through the string s with index i from 0 to s.length() - 1.
  • If the character s.charAt(i) is a vowel, replace the character at resultChars[i] with the vowel from vowels.get(vowelIndex) and increment vowelIndex.
  • Convert the resultChars array back to a string and return it.

Walkthrough

The core idea is to separate the problem into two parts: handling vowels and handling consonants. Since consonants must remain in their original places, we only need to focus on the vowels. We can extract all vowels from the string, sort them independently, and then place them back into the positions that were originally occupied by vowels.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    private boolean isVowel(char c) {        return "aeiouAEIOU".indexOf(c) != -1;    }     public String sortVowels(String s) {        List<Character> vowels = new ArrayList<>();        for (char c : s.toCharArray()) {            if (isVowel(c)) {                vowels.add(c);            }        }         // Sort the collected vowels. Time complexity: O(k log k)        Collections.sort(vowels);         char[] resultChars = s.toCharArray();        int vowelIndex = 0;        for (int i = 0; i < s.length(); i++) {            if (isVowel(s.charAt(i))) {                resultChars[i] = vowels.get(vowelIndex++);            }        }         return new String(resultChars);    }}

Complexity

Time

O(N + k log k), where N is the length of the string and k is the number of vowels. The first loop to collect vowels takes O(N) time. Sorting the list of k vowels takes O(k log k) time. The second loop to place the sorted vowels takes O(N) time. In the worst case, where all characters are vowels (k ≈ N), the complexity is O(N log N).

Space

O(N), where N is the length of the string. We use a list to store the k vowels, which takes O(k) space (where k is the number of vowels). We also use a character array to build the result string, which takes O(N) space. Therefore, the total space complexity is O(k + N), which simplifies to O(N).

Trade-offs

Pros

  • Relatively straightforward to understand and implement.

  • Leverages standard library sorting functions, leading to concise code.

Cons

  • The time complexity is dominated by the sorting step, which is not optimal for this problem's constraints as there is a limited set of characters to sort.

Solutions

public class Solution {    public string SortVowels(string s) {        List < char > vs = new List < char > ();        char[] cs = s.ToCharArray();        foreach(char c in cs) {            if (IsVowel(c)) {                vs.Add(c);            }        }        vs.Sort();        for (int i = 0, j = 0; i < cs.Length; ++i) {            if (IsVowel(cs[i])) {                cs[i] = vs[j++];            }        }        return new string(cs);    }    public bool IsVowel(char c) {        c = char.ToLower(c);        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem