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

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 2

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).