My program times out on large Strings, how could I make it faster?

Question

I am trying to reverse the vowels of a String. My program works but it is slow and times out on large Strings. How could I make it faster? Write a function that takes a string as input and reverse only the vowels of a string.

Example 1: Given s = "hello", return "holle".

Example 2: Given s = "leetcode", return "leotcede".

Note: The vowels does not include the letter "y".

public class Solution {
    public String reverseVowels(String s){

        Set<Character> vowel = new HashSet<>();

        char [] sArray = s.toCharArray();
        vowel.add('a');
        vowel.add('e');
        vowel.add('o');
        vowel.add('i');
        vowel.add('u');
        vowel.add('A');
        vowel.add('E');
        vowel.add('I');
        vowel.add('O');
        vowel.add('U');

        Stack<Character> v = new Stack<>();
        String temp = "";

        int i = 0;
        for (Character c: sArray){
            if (vowel.contains(c)){
                v.push(c);

            }
            i++;
        }
        for (Character c: sArray){
            if (vowel.contains(c)){
               if (!v.empty())
                c = v.pop();
            }
            temp+= c;

        }
        return temp;

    }
}

Edit: I have changed my code to use StringBuilder and now it passes the test cases but it is still slower than 95% of Java solutions, so I will make the other changes to try to make it faster. The slowness in my program is not entirely due to not using StringBuilder. Even with that change, my program is still very slow. It's not a duplicate of other questions.

Answer 1

There's a few things going on here:

1. The Set of vowels is being re-created every time the method is used, and the vowels are likewise being added to it every time (which also probably involves expanding the size of the set); since they aren't going to change, this isn't necessary. (This doesn't make a huge difference, but I thought I'd mention it.)

2. Every char primitive is being auto-boxed into a Character object unnecessarily--in both of your loops and when being added to the Stack of vowels.

3. As the possible duplicate linked by Tom suggests, you'll likely get better performance out of StringBuilder.append(char) rather than the + operator.

Off the top of my head, a better implementation that avoids the above flaws may look like:

private static boolean isVowel(char c) {
    switch (c) {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
        case 'A':
        case 'E':
        case 'I':
        case 'O':
        case 'U':
            return true;
        default: return false;
    }
}

public static String reverseVowels(String s) {
    final char [] sArray = s.toCharArray();
    final StringBuilder reversedString = new StringBuilder();
    final StringBuilder vowels = new StringBuilder();

    int vowelIndex = -1;
    for (char c : sArray) {
        if (isVowel(c)) {
            vowels.append(c);
            ++vowelIndex;
        }
    }

    for (char c : sArray) {
        if (isVowel(c))
            c = vowels.charAt(vowelIndex--);

        reversedString.append(c);
    }
    return reversedString.toString();
}

Answer 2

As Tom has suggested in his comment, the major problem is probably that you are using String instead of StringBuilder, see for example here. Try changing temp to a new StringBuilder, and build your string up that way. With any luck, that will make all the difference. Alternatively, use David's approach and just change the chars in the char array, then do a final toString on that.

Otherwise, if it still isn't fast enough, instead of going through the whole string twice, you could perhaps take note of the positions of each vowel in the string on your first pass through (maybe using a queue of integers?), and then just quickly iterate over the vowel positions, replacing the letter at each spot with the next vowel on your stack. Note that I'm not sure that this will necessarily be faster, but it may be worth a shot. One potential advantage to this approach may be that you can stop processing the string once you have used up all the vowels. So for instance, if you have a string like "aeiouzx...", where the only vowels occur right in the front, once you have gone through your list of vowels, you'll know you are finished and can stop there, potentially avoiding a load of wasted time. Might be an improvement for particular strings.

Hopefully one of these will improve your performance to the desired level.

Answer 3

Here's my example (make sure you give the JVM plenty of heap for this).

Reversing vowels for 320 million characters takes 719ms on my machine. This solution does in-place swapping of vowels using two indices into the char array.

Not the most memory efficient as new String(c) will make a copy of the array as well as String.toCharArray However, pretty fast this one is.

public class Main {

    public static void main(String[] args) {
        Main m = new Main();
        System.out.println(m.reverseVowels("hello"));
        System.out.println(m.reverseVowels("leetcode"));
        char[] longString = new char[320_000_000];
        Arrays.fill(longString, 'e');
        String loooooongString = new String(longString);
        long t = System.currentTimeMillis();
        m.reverseVowels(loooooongString);
        System.out.println("Duration:" + (System.currentTimeMillis() - t));
    }

    String reverseVowels(String s) {
        char[] c = s.toCharArray();
        int i = 0;
        int j = c.length - 1;
        char tmp;
        while (i < j) {
            while (i < j && !isVowel(c[i])) i++;
            while (i < j && !isVowel(c[j])) j--;
            if (i >= j) break;
            tmp = c[i];
            c[i] = c[j];
            c[j] = tmp;
            i++;
            j--;
        }
        return new String(c);
    }

    boolean isVowel(char c) {
        switch (c) {
            case 'a':
            case 'e':
            case 'i':
            case 'o':
            case 'u':
            case 'A':
            case 'E':
            case 'O':
            case 'U':
                return true;
            default:
                return false;
        }
    }
}

Answer 4

I am not sure about performance but try this:

    Set<Character> vowels = new HashSet<>();
    vowels.add('a');
    vowels.add('e');
    vowels.add('o');
    vowels.add('i');
    vowels.add('u');
    vowels.add('A');
    vowels.add('E');
    vowels.add('I');
    vowels.add('O');
    vowels.add('U');

    String str = "KAKEKIKOKUKaKeKiKoKuK";
    char[] strArray1 = str.toCharArray();
    char[] strArray2 = str.toCharArray();
    int pos1 = -1;
    int pos2 = strArray1.length - 1;
    int size = strArray1.length;
    Stack<Character> vowelsStack = new Stack<>();
    boolean isPos1Vowel = false;

    while (true) {
        if (pos2 > -1) {
            if (vowels.contains(strArray2[pos2])) {
                vowelsStack.add(strArray2[pos2]);
            }
            pos2--;
        }
        if (isPos1Vowel) {
            if (!vowelsStack.isEmpty()) {
                strArray1[pos1] = vowelsStack.remove(0);
                pos1++;
                if (pos1 < size) {
                    isPos1Vowel = vowels.contains(strArray1[pos1]);
                } else {
                    break;
                }
            }
        } else {
            pos1++;
            if (pos1 < size) {
                isPos1Vowel = vowels.contains(strArray1[pos1]);
            } else {
                break;
            }
        }
    }

    System.out.println(new String(strArray1));

Please tell me if it works as you want.