algoadvance

Leetcode 345. Reverse Vowels of a String

Problem Statement:

Given a string s, reverse only the vowels of the string and return it.

The vowels are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’, and they can appear in both lower and upper cases (like ‘A’, ‘E’, ‘I’, ‘O’, ‘U’).

Clarifying Questions:

1. Case Sensitivity: Are the vowels ‘A’, ‘E’, ‘I’, ‘O’, ‘U’ considered different from ‘a’, ‘e’, ‘i’, ‘o’, ‘u’?
   • Response: Vowels in both cases should be considered and reversed.
2. Input Constraints: Are there any constraints on the length of the string?
   • Response: There should not be any specific constraints; assume that the input string can be reasonably large.
3. Special Characters: How should non-letter characters be handled?
   • Response: Non-letter characters should remain in their original positions; only vowels are reversed.

Strategy:

1. Identify Vowels: Create a set of vowels for quick look-up.
2. Two-Pointer Technique: Utilize two pointers, one starting from the beginning and the other from the end of the string.
3. Swap Vowels: Move the pointers towards each other, swapping vowels when both pointers encounter them.
4. Stop Condition: The process will stop when the two pointers cross each other.

Code:

import java.util.HashSet;
import java.util.Set;

public class ReverseVowels {
    public static String reverseVowels(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }
        
        Set<Character> vowels = new 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');
        
        char[] chars = s.toCharArray();
        int left = 0;
        int 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) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new String(chars);
    }
    
    public static void main(String[] args) {
        String input = "hello";
        String result = reverseVowels(input);
        System.out.println(result); // Output: "holle"
        
        input = "leetcode";
        result = reverseVowels(input);
        System.out.println(result); // Output: "leotcede"
    }
}

Time Complexity:

• Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once by each pointer).
• Space Complexity: O(1), since we use a fixed amount of extra space for vowels set and two pointers, and the modifications are done in-place.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?