Sort Vowels in a String

Problem

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.

Examples

Example 1:

1
2
3
4
5


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:

1
2
3
4
5


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

Solution

Method 1 - Extract and Sort Vowels

Intuition

The main idea is to keep consonants in their original positions and only sort the vowels. By extracting all vowels, sorting them, and then reinserting them into their original places, we ensure the required order while preserving consonant positions. For example, in “lEetcOde”, the vowels are ‘E’, ’e’, ‘O’, ’e’. Sorting them by ASCII gives ‘E’, ‘O’, ’e’, ’e’, which are then placed back in the string at their respective vowel positions.

Approach

Identify all vowels in the string and record their positions.
Extract the vowels and sort them by ASCII value (case-sensitive).
Iterate through the string, replacing each vowel with the next sorted vowel, while leaving consonants unchanged.
Return the new string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
	string sortVowels(string s) {
		string vowels;
		vector<int> pos;
		string v = "aeiouAEIOU";
		for (int i = 0; i < s.size(); ++i) {
			if (v.find(s[i]) != string::npos) {
				vowels += s[i];
				pos.push_back(i);
			}
		}
		sort(vowels.begin(), vowels.end());
		int j = 0;
		for (int i : pos) s[i] = vowels[j++];
		return s;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func sortVowels(s string) string {
	vowels := []byte{}
	pos := []int{}
	vowelSet := "aeiouAEIOU"
	for i := 0; i < len(s); i++ {
		if strings.ContainsRune(vowelSet, rune(s[i])) {
			vowels = append(vowels, s[i])
			pos = append(pos, i)
		}
	}
	sort.Slice(vowels, func(i, j int) bool { return vowels[i] < vowels[j] })
	ans := []byte(s)
	for i, p := range pos {
		ans[p] = vowels[i]
	}
	return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	public String sortVowels(String s) {
		Set<Character> vowelSet = Set.of('a','e','i','o','u','A','E','I','O','U');
		List<Character> vowels = new ArrayList<>();
		List<Integer> pos = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			if (vowelSet.contains(s.charAt(i))) {
				vowels.add(s.charAt(i));
				pos.add(i);
			}
		}
		Collections.sort(vowels);
		StringBuilder ans = new StringBuilder(s);
		for (int i = 0; i < pos.size(); i++) {
			ans.setCharAt(pos.get(i), vowels.get(i));
		}
		return ans.toString();
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	fun sortVowels(s: String): String {
		val vowels = "aeiouAEIOU"
		val vList = mutableListOf<Char>()
		val pos = mutableListOf<Int>()
		for (i in s.indices) {
			if (s[i] in vowels) {
				vList.add(s[i])
				pos.add(i)
			}
		}
		vList.sort()
		val ans = StringBuilder(s)
		for (i in pos.indices) {
			ans.setCharAt(pos[i], vList[i])
		}
		return ans.toString()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
	def sortVowels(self, s: str) -> str:
		vowels = 'aeiouAEIOU'
		v: list[str] = []
		pos: list[int] = []
		for i, ch in enumerate(s):
			if ch in vowels:
				v.append(ch)
				pos.append(i)
		v.sort()
		ans = list(s)
		for i, p in enumerate(pos):
			ans[p] = v[i]
		return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
	pub fn sort_vowels(s: String) -> String {
		let vowels = "aeiouAEIOU";
		let mut v: Vec<char> = Vec::new();
		let mut pos: Vec<usize> = Vec::new();
		for (i, ch) in s.chars().enumerate() {
			if vowels.contains(ch) {
				v.push(ch);
				pos.push(i);
			}
		}
		v.sort_unstable();
		let mut ans: Vec<char> = s.chars().collect();
		for (i, &p) in pos.iter().enumerate() {
			ans[p] = v[i];
		}
		ans.into_iter().collect()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	sortVowels(s: string): string {
		const vowels = 'aeiouAEIOU';
		const v: string[] = [];
		const pos: number[] = [];
		for (let i = 0; i < s.length; i++) {
			if (vowels.includes(s[i])) {
				v.push(s[i]);
				pos.push(i);
			}
		}
		v.sort();
		const ans = s.split('');
		for (let i = 0; i < pos.length; i++) {
			ans[pos[i]] = v[i];
		}
		return ans.join('');
	}
}

Complexity

⏰ Time complexity: O(n log n) — Extracting vowels and their positions takes O(n), sorting vowels takes O(k log k) where k is the number of vowels (k ≤ n), and reinserting is O(k). Overall, O(n log n) in the worst case.
🧺 Space complexity: O(n) — We use extra space for storing vowel characters and their positions, which is at most O(n).

Problem#

Examples#

Solution#

Method 1 - Extract and Sort Vowels#

Intuition#

Approach#

Code#

Complexity#