How to solve this java problem efficiently [closed]

I am trying to solve this problem and I worked out a solution but its too slow, this is my approach:

1. loop to add all strings in an array
2. loop to concatenate strings based on inputs
3. print out final concatenated string

Which works, but I need a faster approach. I am thinking of trying to determine the order of concatenation of each string, then just print strings based on the order. But I have no idea how to determine the order in the first place. Does anyone have any advice? Thank you!

[SOLVED] thank you guys for the help! I was able to pass the test cases.

Answer

Don’t implement this task literally.

The entire task is designed such that you end up with all N input strings being concatenated in one string, the order determined by the numbers read from System.in.

But the result is not the concatenated string. The result is the output you produce by printing this concatenated string. So you get the same result, i.e. the same output, when you just print the original strings (without separators or line breaks) in the correct order, as if they were concatenated.

Kattio io = new Kattio(System.in, System.out);
int numStrs = io.getInt();
final class StringNode {
    final String s;
    StringNode last = this, next;

    StringNode(String s) {
        this.s = s;
    }

    void append(StringNode s) {
        last.next = s;
        last = s.last;
    }
}
StringNode[] array = new StringNode[numStrs];
for(int i = 0; i < numStrs; i++) array[i] = new StringNode(io.getWord());

int idx = 0;
for(int j = 0; j < numStrs - 1; j++) {
    int a = io.getInt() - 1, b = io.getInt() - 1;
    array[a].append(array[b]);
    idx = a;
}
for(StringNode n = array[idx]; n != null; n = n.next) System.out.print(n.s);
System.out.println();

The main issue with performing the string concatenation literally, is the copying of the characters, potentially over and over again, depending on the given order. In the worst case, you get an order which let’s you copy again the same data you’ve just copied, for every step, ending up at O(N²) time complexity.

The approach above skips the entire task of creating new strings or copying characters, making each step as cheap as two variable assignments.

Note that even if you’re going back to implement the task literally, i.e. to produce a single String, you can do it by replacing the final printing loop by a loop which appends all strings to a single StringBuilder. This will still be a linear operation, as appending all strings in the already determined final order implies copying each string only once, instead of repeatedly.

But as long as the success is measured by the output written to System.out, you don’t need to construct a final String object.