String reversal by word in single pass

Question

Is there any algorithm/technique in which string reversal by words can be done in single pass with time complexity of O(n) and space complexity of O(1).

Answer 1

No, this is not possible in one pass unless you already know how long each word is or are allowed to use some sort of buffer.

Try it:

HELLO SAM
 ^
becomes
SAM HELLO
     ^

If all you know is the E (since this is your first/only pass, and you aren't allowed to store any data), you can't possibly know that it needs to be swapped to where the space character currently is. Once you reach the space and find out where the E belongs, it's too late to retrieve the E again.

Answer 2

If we can get characters in reverse order and each word requires no more than O(1) machine words in memory then to reverse words in a single pass, O(n)-time, O(1)-space algorithm could be used (pseudo-code):

def reverse_words(text):
    word = [] # assume a word requires O(1) machine words
    for character in reversed(text): # single pass (in reverse)
        if character == ' ':
           if word: # print non-empty word
              print(''.join(reversed(word)), end=character)
              word = []
        else:
            word.append(character) # O(1)-time
    if word: # print the first word (in original text) if it is not empty
       print(''.join(reversed(word)))

Example:

>>> reverse_words("this is a string")
string a is this

Note: each character is touched twice: first -- append, second -- print it. To understand why it is still one-pass algorithm, imagine instead of text we are given poplast() function that pops (get and remove) the last character from a character sequence. If it returns None for an empty sequence then the loop would look like:

for character in iter(poplast, None): # call `poplast()` until it returns `None`
    # the rest is the same as in the first loop ..

In this case we can't make more than one pass over the input. It is destroyed on the first pass.

is it possible to change original text itself?

Yes. Again if we can assume that the longest word length is constant (independent from n) i.e., if n grows; the max word length stays the same.

Just read one word at a time from both ends into two temporary buffers. And swap them while keeping track of unused ends due to uneven word sizes on different ends. Only one temporary buffer won't be empty after the swap (the one that has an incomplete word). Fill buffers until the full word is encountered on either ends or the center is reached. Then repeat the swap.

I can't think of an elegant implementation. And I don't see the point of one-pass requirement if we have random access to the input. Look at how tac utility or tail -r (BSD) are implemented (a line plays a role of a single word in this case) for very large files that do not fit in memory.

Answer 3

If considering a word can have maximum number of character is 20, we can achieve O(1) space, O(n) time and one single pass :)

    public static void main(String[] args) {

        reverse("Hello World HaHa");
    }

    public static void reverse(String line) {
        char[] stack = new char[20];
        int index = 0;
        for (int i = line.length() - 1; i >= 0; i--) {
            if (line.charAt(i) != ' ') {
                stack[index++] = line.charAt(i);
            } else {
                while (--index >= 0) {
                    System.out.print(stack[index]);
                }
                System.out.print(' ');
                index = 0;
            }
        }
        if (index > 0) {
            while (--index >= 0) {
                System.out.print(stack[index]);
            }
        }
    }

Note: the actual time complexity is 2n with n is the length of the string, but single pass!