Java O(n) Easy To Understand, Optimal Solution

  • 0

    The point to this question is to use two pointers, lo and hi. They are used to repeatedly identify and swap vowels.

    1. Initialize lo to 0, hi to s.length - 1; they denote the ends of our string
    2. Increment lo until the element at index lo is a vowel.
    3. Decrement hi until the element at index hi is a vowel.
    4. Swap elements at indices lo, hi. Increment lo, decrement hi.
    5. If lo < hi, repeat steps 2-5; otherwise, terminate and return our new string.

    Time Complexity
    The time complexity is O(n) where n is the length of s since we scan through its entire contents, swapping when necessary.

    class Solution {
        public boolean isVowel(char c) {
            c = Character.toLowerCase(c);
            return c == 'a' || c == 'e' || c == 'i' || 
                   c == 'o' || c == 'u';
        public String reverseVowels(String s) {
            int lo = 0;
            int hi = s.length() - 1;
            char [] chS = s.toCharArray();
            // Perform swaps until halfway point
            while (lo < hi) {
                // Keep scanning left until vowel found
                while (lo < hi && !isVowel(chS[lo])) lo++;
                // Keep scanning right until vowel found
                while (lo < hi && !isVowel(chS[hi])) hi--;
                // Swap elements at indicex lo, hi
                char tmp = chS[lo];
                chS[lo] = chS[hi];
                chS[hi] = tmp;
                // Update lo, hi
                lo++; hi--;
            return new String(chS);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.