Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Examples

Example 1:

1
2

Input : s = hello
Output : holle

Example 2:

1
2

Input : s = hello world
Output : hollo werld

Solution

Method 1 - Store the vowels and place them in reverse order

One simple solution is to store all the vowels while scanning the string and placing the vowels in the reverse order in another iteration of string.

Time complexity : O(n) where n = length of string Auxiliary Space : O(v) where v = number of vowels in string

Method 2 - Use 2 pointers

This is a simple problem which can be solved by using two pointers scanning from beginning and end of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public String reverseVowels(String s) {
	ArrayList<Character> vowelSet = new ArrayList<Character>();
	vowelSet.add('a');
	vowelSet.add('e');
	vowelSet.add('i');
	vowelSet.add('o');
	vowelSet.add('u');
	vowelSet.add('A');
	vowelSet.add('E');
	vowelSet.add('I');
	vowelSet.add('O');
	vowelSet.add('U');

	char[] chars = s.toCharArray();

	int left = 0;
	int right = s.length() - 1;

	while (left < right) {
		while (left < right && !vowelSet.contains(chars[left])) {
			left++;
		}

		while (left < right && !vowelSet.contains(chars[right])) {
			right--;
		}

		char temp = chars[left];
		chars[left] = chars[right];
		chars[right] = temp;
		left++;
		right--;

	}

	return new String(chars);
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)