NoPrefixSet.java

/*
No Prefix Set

You are given a list of strings consisting only of lowercase letters. A set of strings is considered a GOOD SET if no string in the set is a prefix of another string. 
If any string is a prefix of another, print BAD SET followed by the first offending string.

Input
 The first line contains an integer n (1 ≤ n ≤ 100,000), the number of strings.
 The next n lines each contain a string words[i] (1 ≤ |words[i]| ≤ 100), composed of lowercase letters.

Output
 Print GOOD SET if the strings form a good set.
 If there is a bad set, print BAD SET followed by the offending string on the next line.
*/

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;


class BranchNode
{
 Map<Character, BranchNode> next = new HashMap<>();
 boolean isEndofWord = false; 
}

class Result 
{
 /*
 * Complete the 'noPrefix' function below.
 *
 * The function accepts STRING_ARRAY words as parameter.
 */
 
 public static void noPrefix(List<String> words)
 {
 // Write your code here
 BranchNode root = new BranchNode();
 
 for(String word : words)
 {
 BranchNode currentNode = root;
 boolean isBadSet = false;
 int n = word.length();
 
 for(int i = 0; i < n; i++)
 {
 char ch = word.charAt(i);
 
 if(currentNode.isEndofWord)
 {
 System.out.println("BAD SET");
 System.out.println(word);
 return;
 }
 
 currentNode = currentNode.next.computeIfAbsent(ch, k -> new BranchNode());
 }
 
 if(!currentNode.next.isEmpty() || currentNode.isEndofWord)
 {
 System.out.println("BAD SET");
 System.out.println(word);
 return;
 }
 
 currentNode.isEndofWord = true;
 }
 
 System.out.println("GOOD SET");
 }
}

public class Solution 
{
 public static void main(String[] args) throws IOException 
 {
 BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

 int n = Integer.parseInt(bufferedReader.readLine().trim());

 List<String> words = IntStream.range(0, n).mapToObj(i -> 
 {
 try 
 {
 return bufferedReader.readLine();
 } 
 
 catch (IOException ex) 
 {
 throw new RuntimeException(ex);
 }
 })
 .collect(toList());

 Result.noPrefix(words);

 bufferedReader.close();
 }
}