0

Link to this problem:

https://www.hackerrank.com/contests/takneek/challenges/maximum-length-substring/problem

The code passes the initial test case but then times out when I go to submit on hacker rank for much larger strings. I have a feeling it's the algorithm I'm using for the unique substrings, how do I cut down this time into something efficient?

My code:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

     LinkedList<Integer> kList = new LinkedList<Integer>();
     LinkedList<String> setout = new LinkedList<String>();
     LinkedList<String> setLex = new LinkedList<String>();

   //Get the original text     
   String text = in.nextLine();
   //Get n from the file
   int n = in.nextInt();
   //Get the next needed items for comparison and order
   for (int i = 0; i < n; i++) {
       kList.add(in.nextInt());
   }

   setout = getAllUniqueSubset(text);
   setLex = sortLexographically(setout);
   int findMax = findMaximumSub(setLex, kList, 0);
 //  System.out.println(setLex);
   System.out.println(findMax);        

}

//Get the unique subset to begin with and return it
    public static LinkedList<String> getAllUniqueSubset(String text) {
    LinkedList<String> set = new LinkedList<String>();
    for (int i = 0; i < text.length(); i++) {
        for (int j = 0; j < text.length() - i; j++) {
            String elem =text.substring(j, j + (i+1));
            if (!set.contains(elem)) {
                set.add(elem);
            }
        }
    }
    return set;


}

public static LinkedList<String> sortLexographically(LinkedList<String> setout){

    for(int i = 0; i < setout.size()-1; ++i) {
        for (int j = i + 1; j < setout.size(); ++j) {     
                 if (setout.get(i).compareTo(setout.get(j)) > 0) {

                     String testLex = setout.get(i);
                     setout.set(i, setout.get(j));
                     setout.set(j, testLex);
                 }         
            } 
    }
 return setout; 
}

public static int findMaximumSub(LinkedList<String> setLex, LinkedList<Integer> kList, int maxCheck){

    for (int i = 0; i < kList.size()-1; i++) {
        if (maxCheck < setLex.get(kList.get(i)).length()) {
            maxCheck = setLex.get(kList.get(i)).length();
        }
    }

 return maxCheck; 
}    

}
7
  • Did you look at the Discussion tab of that contest to see if an answer to your is already there? Commented Feb 23, 2019 at 2:37
  • 2
    Hint: Using contains() on a LinkedList is very bad for performance. Since you have to eliminate duplicate substrings, you should use a Set<String> to collect all substrings. Then copy to array and sort the array. Now finding by index is very quick. No use of LinkedList at all. Commented Feb 23, 2019 at 2:41
  • 1
    There's also TreeSets that are sorted by default, but I could believe HashSets then sort could be more efficient here. I was also going to suggest a Trie, but there's no built-in implementation of that AFAIK. Commented Feb 23, 2019 at 2:45
  • 1
    Task does not look clear, i,e, For example : for the string W='aaab' we have S={'a','aa','aaa','ab','aab','aaab','b'} why aaa is followed by ab not by aab nor aaab Commented Feb 23, 2019 at 4:00
  • 1
    @AlexanderPavlov I guess, it's just a set, without any order. It's just the next sentence mentioning "lexicographically Kth smallest". Commented Feb 23, 2019 at 22:19

0

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.