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.
Example 1:
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation:
The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
- 1 <= s.length <= 3 * 105
- s consist of printable ASCII characters.
My Solution
We can first store all the vowels in a HashSet for fast access. Then we can use the two pointer technique to reverse the vowels. At every iteration, we skip ahead to the next vowel from both pointers and swap them. Finally after swapping all the vowels, we append all the characters of the array to a StringBuilder and return the resulting string.
Time complexity would be O(n) to iterate through the character array. Space complexity would be O(n) also, because we need to maintain a temporary character array to swap the vowels in place. We also need O(n) space for the StringBuilder.
class Solution {
public String reverseVowels(String s) {
Set<Character> vowels = new HashSet<>();
vowels.add('a');
vowels.add('A');
vowels.add('e');
vowels.add('E');
vowels.add('i');
vowels.add('I');
vowels.add('o');
vowels.add('O');
vowels.add('u');
vowels.add('U');
char[] arr = s.toCharArray();
int n = arr.length;
StringBuilder sb = new StringBuilder();
int i = 0;
int j = n-1;
while (i < n && !vowels.contains(arr[i])) {
i++;
}
while (j >= 0 && !vowels.contains(arr[j])) {
j--;
}
while (i < j) {
char c = arr[i];
arr[i] = arr[j];
arr[j] = c;
i++;
j--;
while (i < n && !vowels.contains(arr[i])) {
i++;
}
while (j >= 0 && !vowels.contains(arr[j])) {
j--;
}
}
for (i = 0; i < n; i++) {
sb.append(arr[i]);
}
return sb.toString();
}
}