Reverse Vowels of a String

Problem Statement

LeetCode#345

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

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

Constraints:

• 1 <= s.length <= 3 * 105
• s consist of printable ASCII characters.

Golang Code Reverse Vowels of a String

func reverseVowels(s string) string {
    // copy the input string into result byte slice
    result := []byte(s)

    leftIndex := 0
    rightIndex := len(s)-1

    for leftIndex < rightIndex{
        for  leftIndex < rightIndex && !isVowel(s[leftIndex]){
            leftIndex++
        }

        for leftIndex < rightIndex && !isVowel(s[rightIndex]){
            rightIndex--
        }

        if leftIndex < rightIndex {
            result[leftIndex], result[rightIndex] = s[rightIndex], s[leftIndex]
            leftIndex++
            rightIndex--
        }
    }
    return string(result)
}

func isVowel(b byte) bool {
	return b == 'a' || b == 'e' || b == 'i' || b == 'o' ||
		b == 'u' || b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}

How It Works

1. Two-Pointer Approach:
   • The function uses two pointers, leftIndex starting from the beginning of the string and rightIndex starting from the end.
   • It moves these pointers towards each other, skipping non-vowel characters until it finds a vowel at both pointers.
   • Once vowels are found at both pointers, they are swapped.
2. Vowel Check:
   • The isVowel function checks whether a character is one of the vowels (a, e, i, o, u in both lowercase and uppercase) by direct comparison, which is efficient.
3. Swap and Move:
   • After swapping the vowels, both pointers are moved inward to continue the process until they cross each other.

Example

Given the input "Hello, World!", the output will be "Hollo, Werld!", where the vowels e and o are swapped.

Time Complexity

• O(n): The algorithm makes a single pass through the string, checking each character at most once. This linear time complexity is optimal for this problem.

Space Complexity

• O(n): The result slice is a copy of the original string, so the space complexity is proportional to the length of the string. This could be reduced to O(1) if you modify the string in place (if mutable).

This implementation strikes a good balance between efficiency and clarity, making it a solid choice for reversing vowels in a string.

Visit https: https://codeandalgo.com for more such contents