I was working on the Leetcode problem “Reverse Vowels of a String.”

Here is my first solution:

class Solution {
    public String reverseVowels(String s) {
        String vowels = "aeiouAEIOU";
        char[] arr = s.toCharArray();

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

        while(i < j & i < length & j > 0) {
            while(i < j && vowels.indexOf(arr[i]) == -1) {
                i ++;
            }
            while(j > i && vowels.indexOf(arr[j]) == -1) {
                j --;
            }
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i ++;
            j --;
        }

        return String.valueOf(arr);
    }
}

Since vowels.indexOf() has a time complexity of O(n), where n is the length of the vowels string, I decided to use a faster lookup data structure. Therefore, I implemented a HashSet as follows:

class Solution {
    public String reverseVowels(String s) {
        Set<Character> set = new HashSet<>(Arrays.asList('A','a','E','e','I','i','O','o','U','u'));
        char[] arr = s.toCharArray();

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

        while(i < j & i < length & j > 0) {
            while(i < j && !set.contains(arr[i])) {
                i ++;
            }
            while(i < j && !set.contains(arr[j])) {
                j --;
            }
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i ++;
            j --;
        }

        return String.valueOf(arr);
    }
}

My understanding is that constructing the HashSet with n characters has a time complexity of O(n), and each lookup is O(1). I expected this version to be faster. However, on Leetcode, the first solution finished in 3 ms, while the second one finished in 5 ms.

Why is the second one slower? What is the time complexity of constructing a HashSet with n elements, and how does it affect runtime in this case?