Return to Answer

• 1

• 9.3k
• 1
• 31
• 46

The big performance issue with the current solution is that you're relying on building a String to keep the list of persons that were sent a friend request. A String is immutable in Java so every single operation on it will result in the creation and allocation of a new String. When doing those sorts of repeated allocation in a loop, the performance degrades rapidly.

We need another approach to the problem that doesn't rely on a simple String, and with that, a better data structure.

1. From the problem description, we need to maintain a collection of the friends of John. To pick a suitable data structure, let's examine what we'll need to do with it: we want to add elements to it (each friend name read), and we want to check whether that collection contains a specific name (to not add it to the list of invited persons). Additionally, we don't care about a particular order for this collection. The perfect data structure for that is a HashSet, just like the one you used: it has a constant-time add and contains methods.
2. Then, we also need to maintain a collection of the invited persons, those that were sent the friend request. This is where you used a String and we can do better. Like the above, we want a data structure capable of adding elements (the name of the invited persons), but we also want it to be capable of removing elements (the friend names we might read further down the input). Also, we want to keep an order here, specifically, the order in which the elements were added. For that, LinkedHashSet is perfect: add and remove are both constant-time operations, and it keeps the insertion order.

With that in mind, we can refactor the code to use those data structures:

Collection<String> friends = new HashSet<>(); // to store name of the John's friends
Collection<String> invited = new LinkedHashSet<>();
for (int i = 0; i < N; i++) {
 Scanner scanLine = new Scanner(sc.nextLine());
 String friend = scanLine.next();
 friends.add(friend);
 invited.remove(friend); // potentially remove this invited as it is actually a friend
 scanLine.next(); // ignore the number of friends, we can deduce it anyway
 while (scanLine.hasNext()) {
 String name = scanLine.next();
 if (!friends.contains(name)) {
 invited.add(name);
 }
 }
}

Notice that I changed other things in there:

• When you have the line of input, that is space-separated, you don't need to read manually characters by characters. You can either split(" "), which would return an array of all the tokens space separated, or you can use another Scanner, which by default tokenizes over white spaces, meaning every call to Scanner.next() will return the next word.
• The variables have a meaningful name: friends represent the collection of John's friend and invited represents the collection of persons to whom John sent a friend request.

At the end of the process, we have our wanted collection inside invited, so we can finally print it. For that, we can use String.join starting from Java 8, which is built-in.

System.out.println(String.join(" ", invited));

If you are on a lower Java version, you would need to write the for loop explicitely and use a StringBuilder to construct the result, like shown here. Don't use the old StringTokenizer, it isn't officially deprecated but it is only kept for compatibility reasons and is considered a legacy class.