Recursively moving every lowercase 'x' in a string to the end

Given a string, compute recursively a new string where all the
lowercase 'x' chars have been moved to the end of the string.

endX("xxre") → "rexx"
endX("xxhixx") → "hixxxx"
endX("xhixhix") → "hihixxx"

Here's the initial idea I've had:

public String endX(String str) {
  ArrayList track = new ArrayList();
  return end(str,"",0,track);
}

public String end(String str,String res,int index,ArrayList track)
{
  if(index==str.length() && track.size()==0)
  {
    return res;
  }
  else if(index==str.length() && track.size()!=0)
  {

    return end(str,res+String.valueOf(track.remove(0)),index,track);
  }
  else if(str.charAt(index)=='x')
  {
    track.add(str.charAt(index));
    return end(str,res,index+1,track); 
  }
  else
  {
    return end(str,res+str.charAt(index),index+1,track);
  }

}

I insisted on now using Java substring builtin functions since its complexity is \$O(n)\$. The above solution takes \$O(n)\$ time and \$O(n)+O(n)\$ space complexity.

How I can I optimize my solution further in terms of space and time complexity and total number of variables?

Your solution takes \$O(\frac{(nn)}{2} + \frac{n}{2})\$ space and \$O(\frac{(nn)}{2} + \frac{n}{2})\$ time, where \$n\$ is the amount of characters.

The flaw is trifold:

You make use of recursion. If the compiler doesn't optimize the recursion away, you keep the entire string in memory for each stackframe. This explains why there's a * in the O for space.

Strings are immutable, so when you perform operations on them, you get back a new copy.

When a new copy of a string is made, it has to copy every character in that string to another location in memory. This means you have to copy the entire res variable every time you add to it.

What this all means is that each time you call end with res+str.charAt(index) or res+String.valueOf(track.remove(0)), you have two strings in memory:

• First call to end, with the empty res

• Second call to end with a res of length 1

So if the input string is "xxhixx":

• The first time you add an x to track

• The second time you add an x to track

• The third time you add an h to res, putting a new string of length 1 in memory

• The fourth time you add an i to res, putting a new string of length 2 in memory

• The fifth time you add an x to track

• The sixth time you add an x to track, then the input string is done

• The seventh time you remove an x from track and add it to res, putting a new string of length 3 in memory

• The eighth time you remove an x from track and add it to res, putting a new string of length 4 in memory

• The ninth time you remove an x from track and add it to res, putting a new string of length 5 in memory

• The tenth time you remove an x from track and add it to res, putting a new string of length 6 in memory

• The eleventh time you enter end, both track and str have been processed, and you return res

If we look at the memory usage when you enter end for the eleventh time, you'll see that there are 6 copies of res:

• "h"

• "hi"

• "hix"

• "hixx"

• "hixxx"

• "hixxxx"

That makes the total memory usage \$6+5+4+3+2+1 = 21 \space \text{characters}\$, consistent with \$\frac{(nn)}{2} + \frac{n}{2}\$. \$66 = 36\$, \$\frac{36}{2} = 18\$, \$\frac{6}{2} = 3\$, \$18+3 = 21\$.

If the compiler notices that it can optimize your recursion away, you will not have this issue - the space complexity will be \$O(n)\$. However, internally, it won't be recursion anymore.

Since you're forced to use recursion, what you have is close to the best you can do.

You could convert track to a String - that way, you can just append it to res in one go when you're done.

But we don't like arbitrary requirements, so let's fix the algorithm.

It's pretty simple:

public String endX(String inputString) {
    int xCounter = 0;
    int writeIndex = 0;
    final int size = inputString.length();
    char[] resultArray = new char[size];
    for (int readIndex = 0; readIndex < size; readIndex++) {
        char c = inputString.charAt(readIndex);
        if(c == 'x'){
            xxCounter++;
            resultArray[size - xCounter] = c;
        } else {
            resultArray[writeIndex++] = c;
        }
    }
    return new String(resultArray);
}

It's \$O(2n)\$ in terms of space (1x for resultArray, 1x for the new String). It's \$O(2n)\$ in terms of time (1x for going through the string, another 1x for the new String because it's a constructor).

I'll explain in detail:

We create a character array to store the new string. We then check each character of the input string. If the character is a normal character, write it into the character array and move on to the next. If it's an X, write it at the end of the array (size - 1). The next time you encounter an X, write it at the location 1 before the end of the array (size - 2). And so on.

Lastly, convert to String via the character array constructor.

StackExchange Code Review Q#133215, answer score: 7