3
\$\begingroup\$

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

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<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[]) {
        find_str fin = new find_str();
        Scanner scanner = new Scanner(System.in);
        int num_of_strings = scanner.nextInt();
        for (int i = num_of_strings; --i >=0;) {
            fin.process(scanner.next());
        }
        fin.initialize();
        int num_of_queries = scanner.nextInt();
        for (int i = num_of_queries; --i >=0;) {
            System.out.println(fin.query(scanner.nextInt()-1));
        }
    }

    private String query(int index) {
        if (index < length) {
            return main_ary[index];
        } else {
            return INVALID;
        }
    }

    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);
    }
}
  1. This was written to solve puzzle only
  2. First I thought of creating separate sets for each string and then later unionize all them to get final mainset and then sort them using custom comparator if necessary and later can be retrieved with index.
  3. Later without doing all this nonsense, created tree-set which is populated with substrings on the run, thus combined process of unionizing and sorting.
  4. For retrieving through index I had to make an ArrayList with contents of mainset. I guess this doesn't take much time or memory than other process.
\$\endgroup\$
5
  • 2
    \$\begingroup\$ You been asking all the question for recruitment from interviewstreet.com \$\endgroup\$
    – Pheonix
    Dec 30, 2011 at 19:36
  • \$\begingroup\$ I wouldn't have asked if i didn't solve it, the reason i'm asking is to improvise the code, it wouldn't be good if i asked to solve a puzzle and steal charm myself right? :) FYI, that recruitment is way too beyond me \$\endgroup\$
    – cypronmaya
    Dec 30, 2011 at 19:47
  • \$\begingroup\$ Anyway, i'm still a beginner and trying to solve puzzles , so i could gain some knowledge and to improvise myself in domain :) \$\endgroup\$
    – cypronmaya
    Dec 30, 2011 at 19:50
  • 2
    \$\begingroup\$ @Pheonix, see meta.codereview.stackexchange.com/questions/429/… \$\endgroup\$ Dec 30, 2011 at 22:05
  • \$\begingroup\$ how can i make the process of making substring of each given string,into separate thread ? thus it does parallel functioning and take lesser execution time. \$\endgroup\$
    – cypronmaya
    Dec 31, 2011 at 6:45

1 Answer 1

3
\$\begingroup\$

Just formal way :

Use TreeSet<String> 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.