Interview Street Challenges - Find Strings

find_str.java

package com.interviewstreet.puzzles;

import java.util.ArrayList;
    import java.util.Scanner;
    import java.util.TreeSet;
    
    public class find_str {
    
        private static final String INVALID = "INVALID";
        private TreeSet<String> mainset = new TreeSet<String>();
        private ArrayList<String> array = new ArrayList<String>();
        private String[] main_ary;
        private int length;
        
        public static void main(String args[]) {
            long start=System.currentTimeMillis();
            find_str fin = new find_str();
            System.out.println(System.currentTimeMillis()-start);
            Scanner scanner = new Scanner(System.in);
            int num_of_strings = scanner.nextInt();
            long pr=System.currentTimeMillis();
            
            for (int i = num_of_strings; --i >=0;) {
                fin.process(scanner.next());
            }
            System.out.println("pr took "+(System.currentTimeMillis()-pr));
            long in=System.currentTimeMillis();
            
            fin.initialize();
            System.out.println("in took "+(System.currentTimeMillis()-in));
            
            
            int num_of_queries = scanner.nextInt();
            int length=fin.length;
            long qu=System.currentTimeMillis();
            for (int i = num_of_queries; --i >=0;) {
                int index=scanner.nextInt()-1;
                if(index<length)
                {
                    System.out.println(fin.query(index));
                }
                else
                {
                    System.out.println(INVALID);
                }
            }
            System.out.println("qu took "+(System.currentTimeMillis()-qu));
        }
    
        private String query(int index) {
                return main_ary[index];
               // return array.get(index);
        }
    
        private void process(String input) {
            int len = input.length();
            for (int i = 0; i < len; i++) {
                for (int j = i; j < len; j++) {
                    mainset.add(input.substring(i, j + 1));
                }
            }
        }
    
        private void initialize() {
          length=mainset.size();
            main_ary=(String[]) mainset.toArray(new String[length]);
        //    array.addAll(mainset);
            
        }
    }

Find Strings (25 points)
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, you will be given 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<=i<=n) is denoted by wi and has a length mi. The next line consists of a single integer 'q', denoting the number of queries. Each of the next 'q' lines consists of a single integer 'k'.
Note: The input strings consist only of lowercase english alphabets 'a' - 'z'.

Output:
Output 'q' lines, where the ith line consists of a string which is the answer to the ith query. If the input is invalid ('k' > |S|), output "INVALID" (quotes for clarity) for that case.

Constraints:
1<=n<=50
1<=mi<=2000
1<=q<=500
1<=k<=1000000000

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".

I had the same solution. While testing I get time limit exceeded and 3 out of 7 test cases passed. What was your result?

ya, same problem here, donno what to do, lot of my answers gets same time-out errors.

I think these challenge questions might need more than the usual data structures. Someone at a forum had suggested using suffix tree for this problem.

This problem failed, did you add get optimal solution?