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; 
}    

}
Paula Anne McGrath
  • 71
  • 6
  • Did you look at the Discussion tab of that contest to see if an answer to your is already there? – Andreas Feb 23 '19 at 02:37
  • There are [built-in sorts in Java](https://stackoverflow.com/questions/6247233/java-how-to-sort-a-linked-list) so you don't need your own bubble-sort. But I'd guess that's not that significant. – Rup Feb 23 '19 at 02:40
  • 2
    *Hint:* Using `contains()` on a `LinkedList` is very bad for performance. Since you have to eliminate duplicate substrings, you should use a `Set` 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. – Andreas Feb 23 '19 at 02:41
  • I was considering HashSets as an alternative. I'll try it and get back to you. – Paula Anne McGrath Feb 23 '19 at 02:43
  • 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](https://en.wikipedia.org/wiki/Trie), but there's no built-in implementation of that AFAIK. – Rup Feb 23 '19 at 02: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` – Alexander Pavlov Feb 23 '19 at 04:00
  • 1
    @AlexanderPavlov I guess, it's just a set, without any order. It's just the next sentence mentioning "lexicographically Kth smallest". – maaartinus Feb 23 '19 at 22:19

0 Answers0