Problem
Given a string s, reverse only the vowels in the string and return the resulting string.The vowels are
a, e, i, o, and u, including both uppercase and lowercase forms. All consonants must remain in their original positions.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "hello"Output
"holle"Solution
This solution uses the Two Pointer approach. We convert the string into a character array so that the vowels can be swapped in place.One pointer starts from the beginning and the other starts from the end. The left pointer moves forward until it finds a vowel, while the right pointer moves backward until it finds a vowel.
Once both pointers point to vowels, we swap them and move both pointers toward the center. This process continues until the pointers meet.
class Solution {
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
|| c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
public String reverseVowels(String s) {
int n = s.length();
char[] charArr = s.toCharArray();
int i = 0, j = n - 1;
while (i < j) {
while (i < j && !isVowel(charArr[i])) {
i++;
}
while (i < j && !isVowel(charArr[j])) {
j--;
}
if (i < j) {
char tmp = charArr[i];
charArr[i] = charArr[j];
charArr[j] = tmp;
i++;
j--;
}
}
return new String(charArr);
}
}Complexity
Each character is visited at most once by the two pointers, so the time complexity isO(n), where n is the length of the string.
The character array requires
O(n) space to store the mutable copy of the string. Apart from the output and input representation, the algorithm uses O(1) extra space.