Description
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 <= 105s consists only of letters of the English alphabet in uppercase and lowercase.
Solutions
Solution 1: Sorting
First, we store all the vowels in the string into an array or list vs, then we sort vs.
Next, we traverse the string s, keeping the consonants unchanged. If it is a vowel, we replace it in order with the letters in the vs array.
The time complexity is O(n × log n), and the space complexity is O(n). Where n is the length of the string s.
PythonJavaC++GoTypeScriptRustC#
class Solution:
def sortVowels(self, s: str) -> str:
vs = [c for c in s if c.lower() in "aeiou"]
vs.sort()
cs = list(s)
j = 0
for i, c in enumerate(cs):
if c.lower() in "aeiou":
cs[i] = vs[j]
j += 1
return "".join(cs)(code-box)
class Solution {
public String sortVowels(String s) {
List<Character> vs = new ArrayList<>();
char[] cs = s.toCharArray();
for (char c : cs) {
char d = Character.toLowerCase(c);
if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
vs.add(c);
}
}
Collections.sort(vs);
for (int i = 0, j = 0; i < cs.length; ++i) {
char d = Character.toLowerCase(cs[i]);
if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
cs[i] = vs.get(j++);
}
}
return String.valueOf(cs);
}
}(code-box)
class Solution {
public:
string sortVowels(string s) {
string vs;
for (auto c : s) {
char d = tolower(c);
if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
vs.push_back(c);
}
}
ranges::sort(vs);
for (int i = 0, j = 0; i < s.size(); ++i) {
char d = tolower(s[i]);
if (d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u') {
s[i] = vs[j++];
}
}
return s;
}
};(code-box)
func sortVowels(s string) string {
cs := []byte(s)
vs := []byte{}
for _, c := range cs {
d := c | 32
if d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' {
vs = append(vs, c)
}
}
sort.Slice(vs, func(i, j int) bool { return vs[i] < vs[j] })
j := 0
for i, c := range cs {
d := c | 32
if d == 'a' || d == 'e' || d == 'i' || d == 'o' || d == 'u' {
cs[i] = vs[j]
j++
}
}
return string(cs)
}(code-box)
function sortVowels(s: string): string {
const vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
const vs = s
.split('')
.filter(c => vowels.includes(c))
.sort();
const ans: string[] = [];
let j = 0;
for (const c of s) {
ans.push(vowels.includes(c) ? vs[j++] : c);
}
return ans.join('');
}(code-box)
impl Solution {
pub fn sort_vowels(s: String) -> String {
fn is_vowel(c: char) -> bool {
matches!(c.to_ascii_lowercase(), 'a' | 'e' | 'i' | 'o' | 'u')
}
let mut vs: Vec<char> = s.chars().filter(|&c| is_vowel(c)).collect();
vs.sort_unstable();
let mut cs: Vec<char> = s.chars().collect();
let mut j = 0;
for (i, c) in cs.clone().into_iter().enumerate() {
if is_vowel(c) {
cs[i] = vs[j];
j += 1;
}
}
cs.into_iter().collect()
}
}(code-box)
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';
}
}(code-box)
