345. Reverse Vowels of a String

Hello, reader 👋🏽 ! Welcome to day 34 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 345. Reverse Vowels of a String.

🤔 Problem Statement

• Given a string s, reverse only all the vowels in the string and return it.

• The string can contain vowels in both lower and upper cases. They can also appear more than once.

• E.g.:

  • s = "hello" => holle
  • "leetcode" => leotcede

💬 Thought Process - Two Pointers

• The first thing that comes to the mind when we have to reverse strings and characters is the two pointers technique.
• We can have two pointers: one at the beginning and one at the end of the string.
• Whenever characters at both the pointers are vowels, we swap them and increment left and decrement right pointers simultaneously.
• This process is continued until the left and right pointers become equal.

NOTE: Since in Java, string concatenation is costly, we will have to convert the string to a character array, swap vowels, then convert it back to a string and return that.

👩🏽‍💻 Solution - Two Pointers

class Solution {
    public String reverseVowels(String s) {
        if(s == null || s.length() == 0) {
            return s;
        }

        char[] reversed = s.toCharArray();

        int n = s.length();
        int i = 0, j = n-1;

        while(i < j) {
            char left = reversed[i];
            char right = reversed[j];

            boolean isLeftCharVowel = isVowel(left);
            boolean isRightCharVowel = isVowel(right);

            if(!isLeftCharVowel && !isRightCharVowel) {
                i++;
                j--;
            }
            else if(!isLeftCharVowel) {
                i++;
            }
            else if(!isRightCharVowel) {
                j--;
            }
            else {
                swap(i, j, reversed);
                i++;
                j--;
            }
        }

        return new String(reversed);
    }

    private boolean isVowel(char ch) {
        return (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' 
               || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U');
    }

    private void swap(int left, int right, char[] reversed) {
        char temp = reversed[left];
        reversed[left] = reversed[right];
        reversed[right] = temp;
    }
}

Time Complexity: O(N)
  N = length of string
Space Complexity: O(N)
  N = length of string
    - Since we are using auxiliary space and using a char array

• You can find the link to the GitHub repo for this question here: 345. Reverse Vowels of a String.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!