3
\$\begingroup\$

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<Character> track = new ArrayList<Character>();
  return end(str,"",0,track);
}

public String end(String str,String res,int index,ArrayList<Character> 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?

\$\endgroup\$
  • 1
    \$\begingroup\$ The requirement to use recursion seems like an academic exercise rather than something that would be done in real production code. Is this a homework question? \$\endgroup\$ – 200_success Jun 27 '16 at 18:22
  • 2
    \$\begingroup\$ I don't think that you could meaningfully optimize a recursive solution. If you had to choose between a recursive solution or an efficient solution, which would you rather have? \$\endgroup\$ – 200_success Jun 27 '16 at 18:26
  • \$\begingroup\$ No its not an academic homework but I am preparing for coding interviews. My friend working in a company told that when given a recursion problem in interview we should use subString or o(n) inbuilt functions since it defeats the purpose of using recursion. Hence I am practising without substring in recursion problem. Hence I insisted no to use substring. \$\endgroup\$ – Santhosh Chaitanya Jun 28 '16 at 1:48
7
\$\begingroup\$

Your solution takes \$O(\frac{(n*n)}{2} + \frac{n}{2})\$ space and \$O(\frac{(n*n)}{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:

  1. First call to end, with the empty res
  2. Second call to end with a res of length 1

So if the input string is "xxhixx":

  1. The first time you add an x to track
  2. The second time you add an x to track
  3. The third time you add an h to res, putting a new string of length 1 in memory
  4. The fourth time you add an i to res, putting a new string of length 2 in memory
  5. The fifth time you add an x to track
  6. The sixth time you add an x to track, then the input string is done
  7. The seventh time you remove an x from track and add it to res, putting a new string of length 3 in memory
  8. The eighth time you remove an x from track and add it to res, putting a new string of length 4 in memory
  9. The ninth time you remove an x from track and add it to res, putting a new string of length 5 in memory
  10. The tenth time you remove an x from track and add it to res, putting a new string of length 6 in memory
  11. 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{(n*n)}{2} + \frac{n}{2}\$. \$6*6 = 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.

\$\endgroup\$
  • \$\begingroup\$ Hi Pimgd Thank you for you detailed beautiful explanation but I cannot use iterative solution as I need to solve it only using recursion. But still I did not get why my solution takes o(n*m) space please explain in detail. Thank you \$\endgroup\$ – Santhosh Chaitanya Jun 28 '16 at 1:50
  • \$\begingroup\$ @SanthoshChaitanya I made a mistake, it's actually O((n*n)/2 + n/2) or O(n^2) if you look at the largest term - it's because Strings cannot be changed, so a new copy is made instead every time you add a character to the result string! \$\endgroup\$ – Pimgd Jun 28 '16 at 7:33
6
\$\begingroup\$

You could use StringBuilder to improve performance. Also your solution is more complicated than it needs to be. You can just append all character that aren't x when going "down" in the recursion and then x when it returns "up".

private static void endxRecursive(String str, int index , StringBuilder sb) {
    if(index == str.length()) {
        return;
    }   
    char c = str.charAt(index);
    if(c == 'x') {
        endxRecursive(str, index + 1 , sb);
        sb.append("x");
    } 
    else {
        sb.append(c);
        endxRecursive(str, index + 1 , sb);
    }
}

public static String endx(String str){
    StringBuilder sb = new StringBuilder(str.length());
    endxRecursive(str, 0, sb);
    return sb.toString();
}
\$\endgroup\$
  • \$\begingroup\$ This is indeed the better recursive solution, takes a theoretical O(n) space and O(2n) time. In practice it'll take slightly longer as StringBuilder makes new linked lists to store strings that it later appends. \$\endgroup\$ – Pimgd Jun 28 '16 at 7:35
  • \$\begingroup\$ We are talking java here, I can see no linked list in StringBuilder, it actually operates directly on a char[] so seems pretty slim. \$\endgroup\$ – Tomasz Stanczak Jun 28 '16 at 9:30
  • 1
    \$\begingroup\$ @TomaszStanczak It does...? It does, you're right. Point still stands, but differently: In practice it'll take slightly longer as StringBuilder makes new char arrays to fit the increasing strings. I'll fix it via an edit so that the code in the answer doesn't suffer that flaw. \$\endgroup\$ – Pimgd Jun 28 '16 at 9:47
  • \$\begingroup\$ StringBuilder makes new array only if the current cannot comprise a new character, in this case the array will be created with the proper length from the very beginning (new StringBuilder(str.length())) so no array recreation will happen. \$\endgroup\$ – Tomasz Stanczak Jun 28 '16 at 9:52
  • 1
    \$\begingroup\$ Oh well, my bad, Pimgd was right. The good news is it wouldn't create new array on each character, the recreation of the array doubles its length and adds 2 (int newCapacity = value.length * 2 + 2) - this is just for the completeness, Pimgd's point is still valid. \$\endgroup\$ – Tomasz Stanczak Jun 28 '16 at 10:09
3
\$\begingroup\$

As I noted in the comments, you can either have an elegant recursive solution, or you can have a fast non-recursive solution. You can't really have it both ways when manipulating immutable Java strings.

It is possible, however, to have a recursive solution that is neither elegant nor performant. There is no need for a helper function (which shouldn't be public, by the way). There is also no need for an ArrayList.

@Pimgd has given you the fast solution. I'll show you the academically elegant solution. If there is no x, then you're done. If there is an x, then you plop it at the end.

public static String endX(String str) {
    int pos = str.indexOf('x');
    return (pos < 0) ?
        str :
        str.substring(0, pos) + endX(str.substring(pos + 1)) + "x";
    }
}

Since this is a pure function that does not rely on any object state, it should be static.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.