Write program for Reverse string O(N) time complexity and O(N) space complexity

Question

I have been asked to solve following problem lower than N^2 time complexity and O(N) space complexity:

Write program for the following case Reverse string :

Input:- "Hello World" Output:-"olleH dlroW"

I have tried to figure it out a lot, but whatever I try, I can not come up with a time complexity which is lower than N^2, my code can be seen below, do you have any suggestion how can I come up with a solution with linear time?

Note : it is not allowed to use built-in methods

 public static String stringReverser(String str) {
        if (str == null || str.isEmpty()) {
            throw new IllegalArgumentException();
        }
        if (str.length() < 2) {
            return str;
        }
        String[] strArr = str.split(" ");
        StringBuffer newHolder = new StringBuffer();
        for (int i = 0; i < strArr.length; i++) {
            int j = 0;
            int len = strArr[i].length();
            char[] newCharStr = strArr[i].toCharArray();
            while (j < len) {
                char temp = newCharStr[j];
                newCharStr[j] = newCharStr[len - 1];
                newCharStr[len - 1] = temp;
                len--;
                j++;
            }
            newHolder.append(String.valueOf(newCharStr));
            if(i != strArr.length-1){
                newHolder.append(" ");
            }
        }

        return newHolder.toString();
    }

it was an algorithm question,so it is not allowed to use built-in methods — Gökhan Akduğan, Feb 21 '16 at 22:02

Matt Timmermans · Answer 1 · 2016-02-22T02:45:41.823

Looks like you want to reverse the words in the string, not the whole string. Here you go:

public static String reverseWords(String str)
{
    char[] chars = str.toCharArray();
    int wstart=0;
    for (int pos=0;;pos++)
    {
        if (pos < chars.length && chars[pos]!=' ')
        {
            continue;
        }
        for (int wend=pos-1; wend>wstart; ++wstart,--wend)
        {
            char t=chars[wstart];
            chars[wstart]=chars[wend];
            chars[wend]=t;
        }
        if (pos>=chars.length)
        {
            break;
        }
        wstart=pos+1;
    }
    return String.valueOf(chars);
}

This is the fastest, most space-efficient version you'll find. If this is homework, your prof will know you didn't write it :)

HOWEVER, the one you wrote in the question satisfies the requirements -- O(N) time and O(N) space -- so you probably want to turn in that one. Congratulations!

Since you seem to think it takes O(N^2) time, here's how the time breaks down:

str.split: O(size of output array + size of output strings) = O(str.length()), i.e., O(N)
iterating words: O(number of words) = O(N)
creating and reversing word strings: O(size of word) each, total O(N)
newHolder.append: O(total size of string created) = O(str.length()) = O(N)
newHolder.toString(): O(size of output) = O(N)

So, 5*O(N) = O(N) -- you're good to go.

score 2 · Answer 2 · answered Feb 21 '16 at 23:41

The following algorithm uses O(n) space, and iterates the input string exactly twice (which I believe satisfies the time complexity). One iteration of the input string is to find spaces, the other iteration is to write out the reversed words.

The algorithm goes something like this:

Find the first space (keep track of where the space is)
Write the first word in reverse order (keep track of where the next word starts)

Repeat until end of string

public class ReverseEachWord {

public static void main(String[] args) {
    String input = "Hello World";
    System.out.println(reverseEachWord(input));
}

public static String reverseEachWord(String input) {

    int len = input.length();

    char[] out = new char[len]; // O(n) space
    char[] in = input.toCharArray();

    int spacePos = 0;
    int activePos = 0;

    while (activePos < len) {
        spacePos = activePos+1;
        int spaceFound = -1;
        int offset = 0;
        while (spacePos < len) {
            if (in[spacePos] == ' ') {
                out[spacePos] = ' ';
                spaceFound = 0;
                break;
            }
            spacePos++;
        }
        if (spaceFound < 0) {
            spacePos += spaceFound;
            offset = 1;
        }

        for (int i=0; i<(spacePos-activePos+offset); i++) {
            out[spacePos - i -1 - spaceFound] = in[i+activePos];
        }
        activePos = spacePos+1;

    }

    return Arrays.toString(out);
}

}

Sнаđошƒаӽ · Answer 3 · 2016-02-22T13:33:07.403

You are using split() which contributes additional O(N) time complexity to the solution. Besides, you said built-in methods can't be used!

Here is a pseudo-code for you to try. To the best of my knowledge it has O(N) time complexity and only O(N) space complexity.

i = 0, j = 0
for i = 0 to str.length:
    if str[i] == ' ':
        for k=i-1 to j:    // reverse looping
            print str[k]
        j = i + 1
// printing the last word
for k=i to j:
    print(s[k])

This is my intuition about the complexity. The outer loop gives O(N), and inner loop is once for each word, so it again gives another O(N), meaning the total complexity is O(N). As for space, if you store the characters in another array instead of printing, you would need an array of size N where N is the size of your source string. So space complexity is also O(N).

Here is a java implementation of the pseudo-code:

public static String reverseIt(String str) {

    char[] source = str.toCharArray();
    char[] newArray = new char[source.length];

    int i = 0, j = 0, idx = 0;

    for(i = 0; i < source.length; i++) {
        if(source[i] == ' ') {
            for(int k = i-1; k >= j; k--, idx++) {
                newArray[idx] = source[k];
            }
            j = i + 1;
            newArray[idx++] = ' ';
        }
    }
    for(int k = i-1; k >= j; k--, idx++) {
        newArray[idx] = source[k];
    }

    return new String(newArray);
}

score 0 · Answer 4 · answered Oct 22 '16 at 15:37

public String reverse(String str)
{
char [] chars= str.toCharArray();
int end=chars.length-1, half_len = (int) Math.ceil(chars.length/2);

for(int i=0;i<half_len;i++)
{
    if(chars[i]==' ')
    {
        continue;
    }
    else
    {
        char t=chars[i];
        chars[i]=chars[end];
        chars[end]=t;
    }
    end--;
}
}

Easy to understand :)

Write program for Reverse string O(N) time complexity and O(N) space complexity

4 Answers4