Output strings from a set in lexicographical order

Puzzle Description:


You are given 'n' strings w1, w2, ......, wn. Let Si denote the set of strings formed by considering all unique substrings of the string wi. A substring is defined as a contiguous sequence of one or more characters in the string. More information on substrings can be found here. Let 'S' = {S1 U S2 U .... Sn} .i.e 'S' is a set of strings formed by considering all the unique strings in all sets S1, S2, ..... Sn. You will be given many queries and for each query and an integer 'k'. Your task is to output the lexicographically kth smallest string from the set 'S'.


Input:


The first line of input contains a single integer 'n', denoting the number of strings. Each of the next 'n' lines consists of a string. The string on the ith line (\$1 |S|), output "INVALID" (quotes for clarity) for that case.


Constraints:

• \$1

• \$1

• \$1

• \$1

Sample Input:

2
aab
aac
3
3
8
23

Sample Output:

aab
c
INVALID

Explanation:


For the sample test case, we have 2 strings "aab" and "aac".


S1 = {"a", "aa", "aab", "ab", "b"} . These are the 5 unique substrings of "aab".


S2 = {"a", "aa", "aac", "ac", "c" } . These are the 5 unique substrings of "aac".


Now, S = {S1 U S2} = {"a", "aa", "aab", "aac", "ab", "ac", "b", "c"}. Totally, 8 unique strings are present in the set 'S'.


The lexicographically 3rd smallest string in 'S' is "aab" and the lexicographically 8th smallest string in 'S' is "c". Since there are only 8 distinct substrings, the answer to the last query is "INVALID".


Time-limit: 5 secs

```
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class find_str {

private static final String INVALID = "INVALID";
private TreeSet mainset = new TreeSet();
private ArrayList array = new ArrayList();
private String[] main_ary;
private int length;
public static void main(String arg

Just formal way :

Use TreeSet ts to store S = {S1 U S2} :

• if String is already stored, it returns false,

• you can use ts.toString() to print all values of the Set, separated by ', ' between '[]'

• you have addAll(..), containsAll(..), retainAll(..), ... ready made [and optimized] other tools.

• You can put in Collections.synchronizedSet(s) if you have multi threaded concurrrent jobs.

You can rebuilt/combine your code from JVM, not only from mathematical constraints. ... wheels exist from long time.

StackExchange Code Review Q#7324, answer score: 3