Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Sort Vowels in a String

Problem Statement

Given a string s, return an updated string t such that all consonants in the string s stay in their original positions while any vowels in the string are reordered according to their ASCII values.

The vowels are 'A', 'E', 'I', 'O', and 'U'. These vowels can appear in lowercase or uppercase. All other letters except vowels are consonants.

Examples

  • Example 1:
    • Input: "gamE"
    • Expected Output: "gEma"
    • Justification: The vowels in "gamE" are 'a' and 'E'. Sorting these by ASCII values, 'E' comes before 'a'

.....

.....

.....

Like the course? Get enrolled and start learning!
Dan Anderson

Dan Anderson

· 5 months ago

I think the time complexity analysis for the Python solution is incorrect due to the string concatenation.

result += c # This is O(n), which yields O(n^2) since it is called n times

O(n) could still be achieved if the characters were appended to a list, which was then joined during the return statement:

res = []
res.append(c)
return ''.join(res)