Reversing vowels in a string

Question

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

My code works to reverse the vowels of a string; however, when given a large string, it fails due to "Time Limit Exceeded". How can I make this more efficient so it can handle large inputs?

def reverseVowels(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i] in v:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

Example 2:

Input: s = "leetcode"
Output: "leotcede"

Answer 1

This is your mistake: if s[i] in v:

Simply change that to if s[i].lower() in vowels:. Then it easily gets accepted where I assume you do it.

The problem is that v can be large, making that check slow. For example for input s = 'a'*150000 + 'e'*150000. Your v will be the reverse, so every 'a' will take long to be found in it, as the search goes through all those 'e'. You take quadratic time and it should be linear.

Alternatively, prepare V = set(v) between the loops and use if s[i] in V:.

Bonus: a regex+slicing solution (fastest in my benchmark, fastest alternative I've found is ~27% slower):

def reverseVowels(self, s: str) -> str:
    a = re.split('([aeiouAEIOU])', s)
    a[1::2] = a[-2::-2]
    return ''.join(a)

Answer 2

A set is slightly faster when using in, and a comprehension is slightly faster than a loop with append()

enumerate() allows recording of both the vowel and the vowel's index, ensuring only the vowels are iterated over the second time.

Then you can process just the first half of the list along side the second half of the list (reversed), swapping the characters. This has the side benefit of skipping the middle vowel if there is an odd number.

vowels = [
    (c, ix)
    for ix, c in enumerate(s)
        if c.lower() in {'a', 'e', 'i', 'o', 'u'}
]

s = list(s)

half = len(vowels) // 2

vowel_pairs = zip(
    vowels[:half]
    vowels[-half:][::-1]
)

for a, b in vowel_pairs:
    s[a[1]] = b[0]
    s[b[1]] = a[0]

s = "".join(s)

Demo : https://trinket.io/python3/681a1fb83d

Answer 3

You could convert vowels into a set for a slight improvement, since sets are quicker to check for a certain value than lists.

For your second loop, you don't need to check every character of the input again. Since you already found the vowels, you can also store the location where you found them in your first loop:

vowels = set(['a', 'e', 'i', 'o', 'u'])
s_chars = list(s)

vowels_in_s = []
vowel_indexes_in_s = []
for idx, char in enumerate(s_chars):
    if char.lower() in vowels:
        vowels_in_s.append(char)
        vowel_indexes_in_s.append(idx)

Then to add the vowels in their reversed places, you just reverse the indexes:

vowel_indexes_in_s.reverse()

and replace the vowels using their new indexes:

for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
    s_chars[idx] = char

zip is a useful function that lets you build combined data structures from separate lists. Here we're taking a list of vowels, and a list of indexes, and building [[vowel, index], [vowel, index], ...].

Finally you join the characters like you did before. Add it all together and:

def reverse_vowels(s):
    vowels = set(['a', 'e', 'i', 'o', 'u'])
    s_chars = list(s)

    vowels_in_s = []
    vowel_indexes_in_s = []
    for idx, char in enumerate(s_chars):
        if char.lower() in vowels:
            vowels_in_s.append(char)
            vowel_indexes_in_s.append(idx)

    vowel_indexes_in_s.reverse()

    for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
        s_chars[idx] = char

    return ''.join(s_chars)

Answer 4

Benchmarks

Highly likely this is from LeetCode, so I benchmarked our solutions there. Times from three submissions:

 80.5  77.4  77.6 ms  Jan_B
 12.9  12.5  12.8 ms  MatBailie
  7.8   8.0   8.3 ms  Schmuddi
 11.6  11.7  11.8 ms  Simon_Brahan
 22.1  22.1  22.1 ms  no_comment_minimal_fix_1
 15.7  15.7  15.8 ms  no_comment_minimal_fix_2
  2.7   2.7   2.8 ms  no_comment_numpy
  5.2   4.9   5.3 ms  no_comment_regex

My NumPy solution inspired by Eman Yalpsid's answer takes advantage of the input strings guaranteed to be ASCII.

As LeetCode's time measurements are bad, I did my own, running all solutions on all 480 test cases and printing total times at the end. Full code as submitted

import numpy as np

class Solution:

    def reverseVowels(self, s: str, timess=[]) -> str:
        from time import perf_counter as time
        funcs = [
            self.no_comment_minimal_fix_1,
            self.no_comment_minimal_fix_2,
            self.no_comment_regex,
            self.no_comment_numpy,
            self.Jan_B, 
            self.MatBailie,
            self.Simon_Brahan,
            self.Schmuddi,
        ]
        names = sorted(f.__name__ for f in funcs)
        
        # Measure each solution on this test case
        times = {f: [] for f in names}
        n = 1
        for _ in range(10):
            shuffle(funcs)
            for f in funcs:
                t = time()
                for _ in range(n):
                    f(s)
                times[f.__name__].append(time() - t)
        timess.append(times)
        
        # Check correctness
        result = funcs[0](s)
        for f in funcs:
            if f(s) != result:
                return None

        # After all test cases, show stats
        if len(timess) == 480:
            for f in names:
                print(f'{sum(min(times[f]) for times in timess) / n * 1e3:5.1f} ms ', f)
            return 'intentionally wrong answer so we get to see the output'

        return result

    
    def no_comment_minimal_fix_1(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i].lower() in vowels:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

    
    def no_comment_minimal_fix_2(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        V = set(v)
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i] in V:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

    
    def MatBailie(self, s: str) -> str:
        vowels = [
            (c, ix)
            for ix, c in enumerate(s)
                if c.lower() in {'a', 'e', 'i', 'o', 'u'}
        ]

        s = list(s)

        half = len(vowels) // 2

        vowel_pairs = zip(
            vowels[:half],
            vowels[-half:][::-1]
        )

        for a, b in vowel_pairs:
            s[a[1]] = b[0]
            s[b[1]] = a[0]

        return "".join(s)


    def Simon_Brahan(self, s: str) -> str:
        vowels = set(['a', 'e', 'i', 'o', 'u'])
        s_chars = list(s)

        vowels_in_s = []
        vowel_indexes_in_s = []
        for idx, char in enumerate(s_chars):
            if char.lower() in vowels:
                vowels_in_s.append(char)
                vowel_indexes_in_s.append(idx)

        vowel_indexes_in_s.reverse()

        for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
            s_chars[idx] = char

        return ''.join(s_chars)

    
    def no_comment_regex(self, s: str) -> str:
        a = re.split('([aeiouAEIOU])', s)
        a[1::2] = a[-2::-2]
        return ''.join(a)
    
    
    def no_comment_numpy(self, s: str) -> str:
        b = bytearray(s, 'ascii')
        a = np.frombuffer(b, dtype=np.uint8)
        mask = self.vowel[a]
        a[mask] = a[mask][::-1]
        return b.decode('ascii')
    vowel = np.array([chr(i) in 'aeiouAEIOU' for i in range(128)])

    
    def Jan_B(self, s: str) -> str:
        # set instead of list with both lower and upper case to omit .lower()
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

        # list comprehension instead of loop
        v = [c for c in s if c in vowels]

        # reverse function instead of slicing
        v.reverse()

        # adding to string instead of converting to and from list
        result = ''

        # looping directly over the string
        for char in s:
            if char in vowels:
                char = v.pop(0)
            result += char

        return result


    def Schmuddi(self, s: str) -> str:
 
        # create a set of all potential vowel characters
        vowels = set("aeiouAEIOU")

        # create a generator that will yield the vowels in reverse for each
        # time it's processed:
        backward_vowels = (ch for ch in s[::-1] if ch in vowels)

        # generate a list of characters where each character is either the
        # unaltered character from the original string, or the next character
        # yielded by the generator of reversed vowels (note that the list is
        # returned as a string):
        return "".join(
            [ch if ch not in vowels else next(backward_vowels) 
             for ch in s
            ])

Summarizer script (with fewer results):

from collections import defaultdict

results = '''
 77.7 ms  Jan_B
 13.0 ms  MatBailie
 76.8 ms  Jan_B
 12.5 ms  MatBailie
 78.7 ms  Jan_B
 12.8 ms  MatBailie
'''

times = defaultdict(list)
for line in results.splitlines():
    if line:
        times[line[10:]].append(line[:5])

for name, ts in times.items():
    print(*ts, 'ms ', name)

Attempt This Online!

Answer 5

The logic behind your function is this:

1. Create a list of the vowels in the target string
2. Reverse this list
3. Iterate through the indices pointing to each character of the target string
4. For each index, check if the indexed character is a vowel
5. If yes, retrieve the next vowel from the list of reversed vowel, and replace the indexed character by that retrieved vowel
6. Otherwise, don't change the indexed character

This logic isn't bad, but your implementation is not the most efficient one. Here are suggestions that improve the performance:

• Avoid for loops, and use list comprehensions and generators instead
• Iterate through the string directly instead of using numeric indices
• Avoid using functions inside of loops, list comprehensions, and generators
• Use sets to look up characters instead of lists
• Instead of reversing lists, work on reversed strings instead

Here is my version of the task that makes use of these suggestions. Note that it still follows the same logic as your own solution, but is quite performant. For short to medium strings, it can compete with the bonus answer provided by @no_comment.

def revowel(s: str) -> str:

    # create a set of all potential vowel characters
    vowels = set("aeiouAEIOU")

    # create a generator that will yield the vowels in reverse for each
    # time it's processed:
    backward_vowels = (ch for ch in s[::-1] if ch in vowels)

    # generate a list of characters where each character is either the
    # unaltered character from the original string, or the next character
    # yielded by the generator of reversed vowels (note that the list is
    # returned as a string):
    return "".join(
        [ch if ch not in vowels else next(backward_vowels) 
         for ch in s
        ])

Answer 6

All good things have already been said, alas.

Perhaps a solution using numpy, where you can use arrays to select members of arrays.

import numpy as np

def reverse_vowels(s: str) -> str:
    ss = np.array(list(s))
    vowels = set("aeiouAEIOU")
    
    vowel_mask = np.vectorize(lambda c: c in vowels)(ss)

    ss[vowel_mask] = ss[vowel_mask][::-1]
    
    return "".join(ss)

Perhaps a solution using iterators, but it's essentially a slightly more general version of Schmuddi's answer.

from itertools import filterfalse

def intersperse_by(key_iterator, iterators):
    for key in key_iterator:
        yield next(iterators[key])

def reverse_vowels(s: str) -> str:
    vowels = set("aeiouAEIOU")
    
    def is_vowel(c): return c in vowels
    
    return "".join(
                intersperse_by(
                    map(is_vowel, s), [
                        filterfalse(is_vowel, s),
                        filter(is_vowel, reversed(s)),
                    ]
                )
            )

---

Reviewing my own code, perhaps it could be useful for someone else. I've looked at runtimes for strings of lengths n=10**k, both of my approaches are linear in n. Which is both expected and good. Below, I'm using the runtimes encountered for a random string of length 1_000_000.

no_comment's regexp based solution takes 75 ms. My numpy based solution takes 796 ms, the iterator-based one 452 ms. I don't expect to be able to beat the regexp-based answer, but surely there's room for improvement.

---

Defining a function, and calling it is costly. Indeed,

vowels = set("aeiouAEIOU")

def is_vowel(c): return c in vowels

could have been

is_vowel = set("aeiouAEIOU").__contains__

and this simple change cuts the runtime of the iterator-based answer from 452 ms to 257 ms.

---

Numpy is great, but not for string processing. Duh. Even the simple act of converting the string to an array and back to the string,

"".join(np.array(list(s)))

takes 520 ms, the somewhat better line,

"".join(np.fromiter(s, dtype='<U1'))

takes 437 ms.

Picking more numpy-friendly datatypes,

"".join(map(chr, np.fromiter(map(ord, s), dtype=np.uint8)))

we can reduce this to 195 ms.

which is better, but still won't win us any awards. Nonetheless, using this idea gets the runtime down from 795 ms to 275 ms.

---

The improved codes:

def reverse_vowels(s: str) -> str:
    vowel_mask = np.fromiter(map(set("aeiouAEIOU").__contains__, s), np.bool)
    ss = np.fromiter(map(ord, s), dtype=np.uint8)

    ss[vowel_mask] = ss[vowel_mask][::-1]
    return "".join(map(chr, ss))

def reverse_vowels(s: str) -> str:
    is_vowel = set("aeiouAEIOU").__contains__

    vowel_mask = map(is_vowel, s)
    consonants = filterfalse(is_vowel, s)
    vowels_reversed = filter(is_vowel, reversed(s))
    
    return "".join(intersperse_by(vowel_mask, (consonants, vowels_reversed)))

Answer 7

I instantly thought about looping the characters in the string directly instead of looping by the index and also wanted to test just adding to a string instead of the conversion to and from a list. Reading the other answers I also implemented a set instead of a list containing both upper and lower case vowels. I'm not 100% sure if a list comprehension is always faster than a for loop but it at least looks cleaner to me.

So here is my approach:

def reverse_vowels_fast(s: str) -> str:
    # set instead of list with both lower and upper case to omit .lower()
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

    # list comprehension instead of loop
    v = [c for c in s if c in vowels]

    # reverse function instead of slicing
    v.reverse()

    # adding to string instead of converting to and from list
    result = ''

    # looping directly over the string
    for char in s:
        if char in vowels:
            char = v.pop(0)
        result += char

    return result

I timed it in comparison to the solutions of @MatBailie and @no comment with test_str = 'A slightly longer string to process to see the difference in time better. But only tested manually.'

Function: original_reverse_vowels, execution time: 49700ns
---------
Function: reverse_vowels_no_comment, execution time: 155100ns
Function: reverse_vowels_mat_bailie, execution time: 18100ns
Function: reverse_vowels_fast, execution time: 14400ns

Answer 8

The biggest problem with the code presented is that it does not document what it is to accomplish:
See how your take and MatBailie's do a substitution based on the position in a/the sequence of vowels where others substitute based on the order of vowels in the string.

In addition to using a set to test case-normalised characters, one could use a set containing each vowel in lower as well as upper case.

One could establish the set of vowels used, but the time save in "the substitution pass" is probably less than what's added in preprocessing.

Alternatives: Iterate from both sides concurrently exchanging vowels "on the fly".
When you reach the middle vowel, you're done -
problem: establishing you've reached the middle vowel.

Establish sequence of vowels and its reverse,
find and substitute each.