Reverse Vowels of a String

• Create a helper data structure (like a List or StringBuilder) to store vowels.
• Iterate through the input string s and add every vowel encountered to the helper structure.
• Reverse the collection of vowels.
• Create a StringBuilder for the result.
• Iterate through the input string s again. For each character:
  • If the character is a consonant, append it to the result.
  • If the character is a vowel, append the next vowel from the reversed vowel collection to the result.
• Return the final string from the StringBuilder.

The core idea is to first isolate the vowels from the string, reverse them, and then place them back into the positions where vowels originally appeared.

Algorithm:

1. Create a list or a string to store all the vowels from the input string s.
2. Iterate through s from beginning to end. If a character is a vowel, add it to our vowel collection.
3. After the first pass, our collection contains all vowels in their original order (e.g., for 'IceCreAm', we get ['I', 'e', 'e', 'A']).
4. Now, create a StringBuilder to build the final result.
5. Initialize a pointer to the end of our vowel collection.
6. Iterate through the original string s again. If the character at the current position is a vowel, append the vowel from our collection (using the pointer) to the StringBuilder and move the pointer backward. If it's a consonant, append the original character.
7. Finally, convert the StringBuilder to a string.

Code Snippet:

1class Solution {2    public String reverseVowels(String s) {3        // Helper to check if a character is a vowel4        String vowels = "aeiouAEIOU";5 6        // 1. Collect all vowels from the string7        StringBuilder vowelCollector = new StringBuilder();8        for (char c : s.toCharArray()) {9            if (vowels.indexOf(c) != -1) {10                vowelCollector.append(c);11            }12        }13 14        // 2. Reverse the collected vowels15        vowelCollector.reverse();16 17        // 3. Build the result string18        StringBuilder result = new StringBuilder();19        int vowelIndex = 0;20        for (char c : s.toCharArray()) {21            if (vowels.indexOf(c) != -1) {22                result.append(vowelCollector.charAt(vowelIndex));23                vowelIndex++;24            } else {25                result.append(c);26            }27        }28 29        return result.toString();30    }31}

• Convert the input string s to a character array chars.
• Initialize two pointers, left = 0 and right = s.length() - 1.
• Loop while left < right:
  • Increment left until chars[left] is a vowel.
  • Decrement right until chars[right] is a vowel.
  • If left < right, swap chars[left] and chars[right].
  • Increment left and decrement right.
• Convert the chars array back to a string and return it.

This method avoids the need for extra storage for vowels by performing swaps directly on a character array representation of the string. It uses a single pass where two pointers converge.

Algorithm:

1. Convert the input string s to a character array, chars, since strings are immutable in Java.
2. Initialize a left pointer to 0 and a right pointer to s.length() - 1.
3. Use a while loop to continue as long as left < right.
4. Inside the loop, move the left pointer forward until it points to a vowel.
5. Move the right pointer backward until it points to a vowel.
6. If left is still less than right, it means we have found a pair of vowels. Swap the characters at chars[left] and chars[right].
7. After the swap, increment left and decrement right to continue the search for the next pair.
8. Once the loop finishes (when left >= right), convert the modified character array back into a string and return it.

To efficiently check for vowels, a Set can be used for O(1) lookups.

Code Snippet:

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public String reverseVowels(String s) {7        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));8        char[] chars = s.toCharArray();9        int left = 0;10        int right = s.length() - 1;11 12        while (left < right) {13            // Find the first vowel from the left14            while (left < right && !vowels.contains(chars[left])) {15                left++;16            }17 18            // Find the first vowel from the right19            while (left < right && !vowels.contains(chars[right])) {20                right--;21            }22 23            // Swap the vowels24            if (left < right) {25                char temp = chars[left];26                chars[left] = chars[right];27                chars[right] = temp;28 29                // Move pointers inward30                left++;31                right--;32            }33        }34 35        return new String(chars);36    }37}