Reverse a string in Java, in O(1)?

Question

Is there any facility in the standard Java libraries that, given a CharSequence, produces the reverse in O(1) time?

I guess this is "easy" to implement, just wondering whether it already exists. (I suspect the reason this is not offered is because the "easy" way would actually break multi-char code-points - but in many cases we know we are not dealing with those).

Thanks

Update Heh, it's a bit amusing that most thought this "impossible", good work guys! Well, actually it is (conceptually) trivial - pseudojava follows to make it clear:

class MyReverseString extends String { //of course I can't extend String!
   final String delegate;
   MyReverseString(String delegate) { this.delegate = delegate; }

   int length() { return delegate.length(); }

   int charAt(int i) { return delegate.charAt(delegate.length() - 1 - i); }
}

I'm leaving the question open for some more, just in the rare event that something like the obvious solution (e.g. see Jon Skeet's one) already exists in the JDK and someone knows about it. (Again, highly unlikely due to those nasty code points).

Edit Probably the confusion came from me having "string" in the title (but not String!), whereas I only ask for "the reverse of a CharSequence". If you were confused, sorry. I would have hoped the O(1) part would make exactly clear what was being asked for.

And by the way, this was the question that made me ask this one. (That's a case where it would be easier to run a regex from right-to-left, not left-to-right, so there may be some practical value even for the simple/broken-codepoints implementation)

Answer 1

This is impossible. In order to reverse a string you must process each character at least once, thus, it must be at least O(n).

Answer 2

StringBuffer has a reverse: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()

BTW, I assume you meant O(n) because O(1) (as other people have mentioned) is obviously impossible.

Answer 3

string result = new StringBuffer(yourString).reverse().toString();

Depending on what you understand under O(1) it does not seem possible since even reading the string once needs O(n) with n being the number of characters in the string.

Answer 4

Well, you can easily produce an implementation of CharSequence which returns the same length, and when asked for a particular character returns the one at length-index-1. toString() becomes O(n) of course...

Creating that reversed CharSequence would be O(1) - all it's got to do is store a reference to the original CharSequence, after all. Iterating over all the characters within the sequence is going to be O(n) though, obviously.

Note that creating a reversed CharSequence (as per the body of your question) is not the same as creating a reversed String (as per the title of your question). Actually producing the String is O(n), and has to be.

Sample code, mostly untested:

public final class ReverseCharSequence implements CharSequence
{
    private final CharSequence original;

    public ReverseCharSequence(CharSequence original)
    {
        this.original = original;
    }

    public int length()
    {
        return original.length();
    }

    public char charAt(int index)
    {
        return original.charAt(original.length() - index - 1);
    }

    public CharSequence subSequence(int start, int end)
    {
        int originalEnd = original.length() - start;
        int originalStart = original.length() - end;
        return new ReverseCharSequence(
            original.subSequence(originalStart, originalEnd));
    }

    public String toString()
    {
        return new StringBuilder(this).toString();
    }
}

Answer 5

How all the others wrote already, it's not possible in O(1) time, since you do have to look at least at every character once.

But if you meant how to do it in O(1) space, here's it: If you want to do it in O(1) space, you can obviously not allocate a new string of the same length, but you have to swap the characters in-place.

So all you have to do is iterate from left to the middle of the string and simultaneously from right to the middle and swap elements. Pseudocode (Conventions: Let string s be accessible at the n-th character via s[n]. If s has length k, we say it has elements 0 to k-1):

for i=0; i<len(s)/2; ++i{
 char tmp = s[i]
 s[i] = s[len(s)-1-i]
 s[len(s)-1-i] = tmp
}

So you see, all you need is a auxiliary variable tmp containing your current char for swapping it, so you can do it in O(1) space.

Answer 6

Jon Skeet's solution is likely most efficient. But if you just want a quick and dirty, this should do it and I don't think it would be far behind in performance.

StringBuffer reverse=new StringBuffer(original.toString()).reverse();

A StringBuffer is a CharSequence, so if you're implying that the result must be a CharSequence, this is.

Well, this might be faster than Mr Skeet's solution if you examine the sequence multiple times, as it eliminates the overhead of the calculation to find the right char position every time you read a character. It's going to do it just once per character.

If I was going to do a billion of these, maybe I'd do a benchmark.