Sort Vowels in a String (LeetCode)

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.

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.

Solution 1 (Slower)

 public string SortVowels(string s) {
		// I will code it as if i don't know the ascii value of chars
		string pattern = @"[aeiouAEIOU]";
		var regex = new Regex(pattern, RegexOptions.Compiled);
		var matches = Regex.Matches(s, pattern, RegexOptions.Compiled).ToList();
		var vowelsCountGroup = matches.GroupBy(g => g.Value).OrderBy(o => o.Key[0]).ToList();
		var totalReplaced = 0;
		foreach(var group in vowelsCountGroup)
		{
            var count = group.Count();
			s = regex.Replace(s, group.Key, count, matches.ElementAt(totalReplaced).Index);
			totalReplaced += count;
		}
		return s;
    }

Solution 2 (Faster)

public string SortVowels(string s) {
		// I will code it as if i don't know the ascii value of chars
        var vowelsCountDic = new SortedDictionary<char, int>();
        var allVowelIndexes = new List<int>();
        var newStr = new StringBuilder(s);
        int currentCount = 0;
        var vowles = new int[] { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };

        // count all the vowel chars
        for (int i = 0; i < s.Length; i++)
        {
            var cha = newStr[i];
            if (vowles.Contains(cha))
            {
                vowelsCountDic.TryGetValue(cha, out currentCount);
                allVowelIndexes.Add(i);
                if (currentCount != 0)
                {
                    vowelsCountDic[cha] += 1;
                }
                else
                {
                    vowelsCountDic.Add(cha, 1);
                }
                newStr[i] = ' ';
            }
        }

        // add the vowel characters at their right places
        var replacedTill = 0;
        var totalReplaced = 0;
        var nextIndexTillWhichNeedToReplace = 0;
        foreach (var tupVal in vowelsCountDic)
        {
            nextIndexTillWhichNeedToReplace = allVowelIndexes[tupVal.Value + totalReplaced - 1];
            newStr.Replace(' ', (char)tupVal.Key, replacedTill, nextIndexTillWhichNeedToReplace - replacedTill + 1);
            replacedTill = nextIndexTillWhichNeedToReplace;
            totalReplaced += tupVal.Value;
        }

        return newStr.ToString();
    }

We may still improve the performance, by utilising the regex for getting the count of vowels. Haven’t tried it. But you can.