Lexicographically Least Substring (Hard)

View as PDF
Submit solution
Points: 15
Time limit: 1.8s
Memory limit: 256M
Problem type
Brute Force Practice 2 — Hard Version

You have a string (indexed from 0) with no more than 10^6 lowercase characters. Find the lexicographically least substring with a length of at least K. A string S is said to be lexicographically smaller than a string T if |S| < |T| and S is a prefix of T or S_k < T_k and S_i = T_i (0 \le i < k, 0 \le k < \min(|S|, |T|)). Here, |X| denotes the length of the string.

Input Specification

The first line will have the string.

The second line will have K.

Output Specification

Print the lexicographically least substring of length at least K.

Sample Input

iloveprogramming
4

Sample Output

ammi

Comments


  • 1
    ZippIE  commented on Nov. 29, 2017, 3:48 a.m.

    My code TLEs on the 16th case, but ACs on the rest. Any tips?


    • 1
      Genius3435  commented on May 21, 2021, 3:55 a.m.

      In my submission, I had the same thing. I don't want to spoil my solution, but I was sorting a lot of pair's, which maybe made the comparisons take too long (constant factor). I fixed it weirdly by using qsort instead of std::sort in C++.


  • 6
    kobortor  commented on Feb. 15, 2015, 4:43 a.m. ← edited

    What should my program output if the size of K is larger than the given string.


    • 7
      FatalEagle  commented on Feb. 15, 2015, 5:02 a.m.

      You may assume K \le |S|


  • 0
    raggarwal  commented on Nov. 24, 2014, 5:21 a.m.

    IS this a true brute force problem? keep getting memory limits on mostly all the test cases when trying to brute force it


    • 3
      FatalEagle  commented on Nov. 25, 2014, 1:28 a.m.

      No, it's not actually brute force -- it's just a harder version of the brute force practice (the name is a bit misleading).


      • -1
        raggarwal  commented on Nov. 25, 2014, 3:40 a.m.

        Ok, Would this be something along the lines of a suffix tree then?


        • 0
          FatalEagle  commented on Nov. 25, 2014, 3:52 a.m. ← edited

          You can theoretically solve it with an \mathcal{O}(N) suffix tree, but there are algorithms with lower constant factors.


          • 0
            raggarwal  commented on Nov. 25, 2014, 8:40 p.m.

            Mind telling me of such algorithms? I cant think of any :(


            • -1
              FatalEagle  commented on Nov. 25, 2014, 10:12 p.m.

              One example is the suffix array. If you're going to use that, you'd need a very fast algorithm, like DC3 implemented in a very efficient manner.


              • -1
                raggarwal  commented on Nov. 25, 2014, 11:08 p.m.

                Nvm, its not working, still memory limits. Wouldn't using a suffix array still take lots of memory? Because after the suffix array is created, you need to sort it then iterate through the list.


                • -1
                  FatalEagle  commented on Nov. 25, 2014, 11:09 p.m. ← edited

                  Your algorithm for suffix array is extremely slow naive brute force \mathcal{O}(N^2 \log N). There are \mathcal{O}(N) algorithms for suffix array, such as DC3. You probably have to implement it in C++.


              • -2
                raggarwal  commented on Nov. 25, 2014, 10:22 p.m.

                I originally thought of a suffix array, however how would you find the Lexicographically Least Substring via that. Wouldnt you need to store all possible answers in an array and sort it?


                • -2
                  raggarwal  commented on Nov. 25, 2014, 10:24 p.m.

                  NVM figured it out myself...... suffix array is sorted initially.

                  Thanks though!