Lexicographically Least Substring (Hard)

View as PDF

Submit solution

Points: 15
Time limit: 4.0s
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.


The first line will have the string.

The second line will have K.


Print the lexicographically least substring of length at least K.

Sample Input


Sample Output



  • 0
    ZippIE  commented on Nov. 28, 2017, 10:48 p.m.

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

  • -2
    d  commented on Jan. 6, 2016, 10:47 p.m.
    Weak test cases

    O(|S|*K) passes.

    • 0
      FatalEagle  commented on Jan. 7, 2016, 12:38 a.m. edit 3

      I'm pretty sure your algorithm has complexity \mathcal{O}(26 \times K + N), but regardless of that your algorithm is simply wrong.


  • 4
    kobortor  commented on Feb. 14, 2015, 11:43 p.m.

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

    • -1
      FatalEagle  commented on Feb. 15, 2015, 12:02 a.m.

      You may assume K \le |S|

  • 0
    raggarwal  commented on Nov. 24, 2014, 12:21 a.m.
    brute force?

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

    • -1
      FatalEagle  commented on Nov. 24, 2014, 8:28 p.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. 24, 2014, 10:40 p.m.

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

        • -1
          FatalEagle  commented on Nov. 24, 2014, 10:52 p.m.

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

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

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

            • -1
              FatalEagle  commented on Nov. 25, 2014, 5: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, 6: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, 6:09 p.m.

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

                  • 0
                    quantum  commented on Nov. 25, 2014, 8:37 p.m.

                    We support math here, so O(N^2 \log N) and O(N).

              • -1
                raggarwal  commented on Nov. 25, 2014, 5: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?

                • -1
                  raggarwal  commented on Nov. 25, 2014, 5:24 p.m.

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

                  Thanks though!