Reverse String or Reverse Vowels of a String Problem

This comprehensive write-up covers the classic string reversal problem with a focus on efficiently reversing vowels in a string, demonstrating optimal two-pointer techniques and handling edge cases effectively.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input array in-place, or do we need to return a new string?
2. What is the expected time complexity constraint? Are we aiming for O(n) or better?
3. Do we need to handle Unicode characters beyond ASCII, or can we assume standard ASCII/English letters?
4. What should we do with empty strings or single-character strings?
5. Should we preserve the case of vowels (e.g., 'A' vs 'a') or treat them as equivalent?

Restatement of the problem: Given a string, reverse only the vowels in the string while keeping all other characters in their original positions. Vowels are defined as 'a', 'e', 'i', 'o', 'u' and their uppercase counterparts.

Input and output specification:

• Input: A string of length n (0 ≤ n ≤ 3 × 10⁵)
• Output: The same string with only vowels reversed in order
• Example: Input "hello" → Output "holle"

Constraints and assumptions:

• The string contains only printable ASCII characters
• We can assume standard English vowels (a, e, i, o, u, A, E, I, O, U)
• The string can be empty or contain only vowels or only consonants
• We don't need to preserve the original string structure, so in-place modification is acceptable

Data shape and hidden structure: The problem has a two-pointer pattern where we identify vowels from both ends of the string and swap them. The hidden structure is that we're essentially maintaining a symmetric relationship between positions in the string, where vowels from opposite ends should be swapped to maintain their relative order in reverse.

Key insight: This is a classic two-pointer problem where we traverse from both ends toward the center, identifying vowels and swapping them when found, while skipping non-vowel characters.

2. Pattern Recognition

The most likely pattern here is Two Pointers with String Manipulation.

The wording that signals this pattern includes:

• "Reverse" - suggests we need to swap elements from both ends
• "Vowels" - indicates we only care about specific characters, not all characters
• "String" - suggests we're working with a sequence that can be traversed from both ends

This problem fits the Two Pointers pattern because:

1. We need to process the string from both ends simultaneously
2. We only want to modify specific elements (vowels) while leaving others in place
3. The operation is symmetric - we're essentially reversing the order of vowels while keeping consonants in their original positions

The core insight is that we don't need to collect all vowels first and then reverse them. Instead, we can use two pointers moving inward from both ends of the string, swapping vowels when both pointers find one. This approach allows us to solve it in a single pass with O(1) extra space.

The key insight is recognizing that we're not truly reversing the entire string, but rather reversing only the vowels while maintaining the relative positions of all consonants. This constraint makes the two-pointer approach optimal and clean.

This pattern is commonly seen in problems like "Reverse String", "Remove Duplicates", or "Partition Array" where we need to process elements from both ends while maintaining some invariants.

3. Approach Evolution

My first instinct is to use a two-pointer technique because we need to swap elements from both ends of the string toward the center. This approach is intuitive and naturally handles the constraint that we only want to reverse vowels, not all characters. But that's O(n²) in the brute force approach because we'd have to check each character against all vowels repeatedly.

Let me think about how to optimize this. I notice that if I maintain a set of vowels and use two pointers moving inward from both ends, I can reduce it to O(n) time complexity. The key insight is that we only care about swapping vowels, so I can skip consonants entirely.

The brute force approach would be to:

1. Collect all vowels in order
2. Reverse that collection
3. Go through the string again and replace each vowel with the corresponding one from the reversed list

This is O(n²) because for each character, we might need to search through the vowel list to find if it's a vowel.

The improved approach uses two pointers:

1. Start with left pointer at 0 and right pointer at string length - 1
2. Move left pointer forward until it finds a vowel
3. Move right pointer backward until it finds a vowel
4. Swap the vowels at these positions
5. Continue until pointers meet

This is O(n) because each character is visited at most once, and vowel checking is O(1) with a HashSet lookup.

The final approach uses two pointers to traverse the string from both ends, maintaining the invariant that we only swap vowels. We can optimize by using a HashSet to store vowels for O(1) lookup, and we never process the same character twice.

Important invariants that must hold:

• Left pointer always points to a vowel or is at or before right pointer
• Right pointer always points to a vowel or is at or after left pointer
• When we swap, we maintain the constraint that only vowels are reversed
• The process terminates when left and right pointers cross or meet

This approach is optimal because we make exactly one pass through the string, and each operation (vowel check, swap) is constant time.

4. Data Structure Choice

For this problem, I'll use a two-pointer approach with in-place modification. The primary data structure is a char[] array to represent the input string, which allows for efficient in-place character swapping without additional space overhead.

Why char[] is the right choice:

• In-place modification: We can directly swap characters in the array without creating a new string
• O(1) space complexity: No additional memory allocation beyond the input array
• Efficient access: O(1) random access to any character position
• Memory locality: Characters are stored contiguously in memory

Why not other structures:

• StringBuilder/String: Would require O(n) extra space for creating new strings during swaps
• Stack: While we could use a stack to collect vowels and then rebuild, it would add O(n) space complexity
• ArrayList: Would introduce unnecessary overhead compared to direct array indexing

Helper structure:

I'll use a simple Set<Character> containing all vowels (both lowercase and uppercase) as a lookup helper to efficiently check if a character is a vowel in O(1) time.

The combination of char[] for the main operation and Set<Character> for vowel lookup provides optimal space efficiency while maintaining clean, readable code.

// Primary data structure: char[] for in-place modification
char[] chars = s.toCharArray();

// Helper structure: Set for O(1) vowel lookup
Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

5. Algorithm Walkthrough

Let me trace through the algorithm with the example input "hello":

1. Initialization:

   • left = 0, right = 4 (indices of 'h' and 'o')
   • vowels = {'a','e','i','o','u','A','E','I','O','U'}
   • chars = ['h','e','l','l','o']

2. First iteration (left=0, right=4):

   • chars[left] = 'h' is not a vowel, so we increment left to 1
   • chars[right] = 'o' is a vowel, so we continue to next step

3. Second iteration (left=1, right=4):

   • chars[left] = 'e' is a vowel and chars[right] = 'o' is a vowel
   • Swap these characters: chars[1] and chars[4] become 'o' and 'e'
   • Result: ['h','o','l','l','e']
   • Increment left to 2, decrement right to 3

4. Third iteration (left=2, right=3):

   • chars[left] = 'l' is not a vowel, increment left to 3
   • chars[right] = 'l' is not a vowel, decrement right to 2

5. Termination (left=3, right=2):

   • Since left >= right, we stop the loop
   • Final result: ['h','o','l','l','e']

The algorithm correctly handles the case where we have a mixed string with vowels at different positions, swapping only the vowel characters while preserving consonants in their relative positions.

The key invariant maintained throughout is that all characters to the left of left are either consonants or already swapped vowels, and all characters to the right of right are either consonants or already swapped vowels. This ensures we don't process the same vowel twice and that our swap operation is safe.

6. Java Solution

public class Solution {
    public String reverseVowels(String s) {
        // Handle edge cases
        if (s == null || s.length() <= 1) {
            return s;
        }
        
        // Convert string to char array for in-place modification
        char[] chars = s.toCharArray();
        
        // Two pointers approach
        int left = 0;
        int right = chars.length - 1;
        
        // Set of vowels for O(1) lookup
        java.util.Set<Character> vowels = new java.util.HashSet<>();
        vowels.add('a'); vowels.add('e'); vowels.add('i'); vowels.add('o'); vowels.add('u');
        vowels.add('A'); vowels.add('E'); vowels.add('I'); vowels.add('O'); vowels.add('U');
        
        // Main loop - continue while pointers haven't crossed
        while (left < right) {
            // Move left pointer to next vowel
            while (left < right && !vowels.contains(chars[left])) {
                left++;
            }
            
            // Move right pointer to previous vowel
            while (left < right && !vowels.contains(chars[right])) {
                right--;
            }
            
            // Swap vowels at left and right positions
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                
                // Move pointers inward
                left++;
                right--;
            }
        }
        
        // Convert back to string and return
        return new String(chars);
    }
}

This solution uses a two-pointer technique with O(n) time complexity and O(n) space complexity for the character array. The key insight is to process vowels from both ends toward the center, swapping them when found. The algorithm handles all edge cases including empty strings, single characters, and strings with no vowels.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the character array with two pointers moving toward each other. Each character is visited at most twice - once by each pointer. The vowel checking operation is O(1) since we're using a HashSet lookup, and swapping operations are constant time. Therefore, the overall time complexity is linear in the length of the input string.

Space Complexity: O(1)

The space usage is constant regardless of input size. We only use a fixed-size HashSet to store vowels, which contains exactly 10 characters (5 lowercase + 5 uppercase). The two integer pointers and temporary variables for swapping consume constant space. No additional data structures grow with input size.

Why these bounds are correct:

The linear time complexity is optimal for this problem since we must examine each character at least once to determine if it's a vowel and potentially swap it. The constant space complexity is achieved by avoiding any data structures that scale with input size - the HashSet size is fixed and independent of input length.

The solution is optimal because:

1. We cannot do better than O(n) time since we must process all characters
2. We cannot use less than O(1) space since we need to store the vowel set and maintain constant extra variables
3. The approach avoids any unnecessary operations or data structure overhead

This represents the best possible trade-off between time and space efficiency for this problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return empty string without any operations
• Single character: Should return the same character (no vowels to swap)
• Two characters with one vowel: Should swap correctly

Duplicate Values and Repeated States

• Multiple vowels in sequence: Algorithm must handle consecutive vowels properly
• Same vowel repeated: Should not interfere with swapping logic
• No vowels present: String should remain unchanged

Boundary Conditions

• First character is vowel: Should be swapped with last vowel from the right side
• Last character is vowel: Should be swapped with first vowel from the left side
• Only first and last characters are vowels: Should swap these two positions

Common Implementation Mistakes

• Not handling case sensitivity properly: The problem asks to reverse vowels, not just any letters - only a, e, i, o, u (both cases)
• Index out of bounds: Not properly checking array bounds when swapping characters
• Infinite loop: When using while loops, ensuring proper termination conditions
• Incorrect pointer movement: Moving pointers in wrong direction or not skipping non-vowels correctly
• Not using proper vowel checking: Using character comparison instead of proper set lookup

Implementation-specific Pitfalls

• Mutating input string: String is immutable in Java, so we must convert to char array or use StringBuilder
• Incorrect character comparison: Using == instead of Character.toLowerCase() for case-insensitive vowel matching
• Off-by-one errors: When calculating positions in the character array
• Not handling mixed case properly: "Aa" should become "aA", not "AA" or "aa"

// Example of incorrect handling:
// if (s.charAt(left) == 'a' || s.charAt(left) == 'e' || ...) { ... }
// Should use Character.toLowerCase() for case-insensitive matching

9. Alternative Approaches

There are several alternative approaches to solving the reverse vowels problem, each with different trade-offs:

Two-Pointer with HashSet Approach: Instead of using a hardcoded string of vowels, we could use a HashSet<Character> to store vowels for O(1) lookup. This approach is more maintainable if we need to handle additional characters later, but has the same time complexity O(n) and space complexity O(1) since we're only storing 10 vowels.

public class Solution {
    public String reverseVowels(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        
        while (left < right) {
            while (left < right && !vowels.contains(chars[left])) left++;
            while (left < right && !vowels.contains(chars[right])) right--;
            
            if (left < right) {
                swap(chars, left, right);
                left++;
                right--;
            }
        }
        
        return new String(chars);
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

Stack-Based Approach: We could first collect all vowels in a stack, then iterate through the string again replacing each vowel with one from the stack. This approach uses O(n) space and is less efficient due to two passes, but it's conceptually simpler to understand.

Recursive Approach: A recursive solution that processes the string from both ends, swapping vowels when found. While elegant, it uses O(n) call stack space and is less efficient than the iterative two-pointer approach.

The original two-pointer approach with string lookup is preferred because it's most efficient in both time and space, requiring only one pass through the string with constant extra space. The HashSet approach offers better maintainability but same complexity, while alternatives like stack or recursion add unnecessary overhead.

10. Test Cases

public class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() <= 1) return s;
        
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        
        while (left < right) {
            // Skip non-vowels from left
            while (left < right && !vowels.contains(chars[left])) {
                left++;
            }
            
            // Skip non-vowels from right
            while (left < right && !vowels.contains(chars[right])) {
                right--;
            }
            
            // Swap vowels
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new String(chars);
    }
}

Sample Test Cases

Basic Example:

// Input: "hello"
// Expected Output: "holle"
// Explanation: 'e' and 'o' are swapped

Case with Mixed Case:

// Input: "leetcode"
// Expected Output: "coettlecd"
// Explanation: 'e' and 'e' at positions 1 and 7 are swapped

Edge Case - Empty String:

// Input: ""
// Expected Output: ""

Edge Case - Single Character:

// Input: "a"
// Expected Output: "a"

Edge Case - No Vowels:

// Input: "bcdfg"
// Expected Output: "bcdfg"

Edge Case - All Vowels:

// Input: "aeiou"
// Expected Output: "uoiea"

Tricky Case - Consecutive Vowels:

// Input: "ae"
// Expected Output: "ea"

Boundary Case - Only First/Last Are Vowels:

// Input: "Ae"
// Expected Output: "eA"

These test cases cover the essential scenarios including edge cases, boundary conditions, and various combinations of vowels and consonants to ensure robustness of the solution.

11. Final Summary

The core insight is that we can efficiently reverse the vowels in a string by using a two-pointer technique to identify and swap vowels from both ends, maintaining O(n) time complexity while using only O(1) extra space. This approach works because we only need to process each character at most once and can leverage the symmetric nature of the problem to avoid unnecessary computations. The solution is optimal as it achieves the best possible time and space complexity for this problem, with no room for improvement in either dimension.