## Lexicographically Least Substring (Hard)

View as PDF

Points: 15
Time limit: 4.0s
Memory limit: 256M

Problem type

##### Brute Force Practice 2 — Hard Version

You have a string (indexed from ) with no more than lowercase characters. Find the lexicographically least substring with a length of at least . A string is said to be lexicographically smaller than a string if and is a prefix of or and . Here, denotes the length of the string.

#### Input

The first line will have the string.

The second line will have .

#### Output

Print the lexicographically least substring of length at least .

#### Sample Input

iloveprogramming
4

#### Sample Output

ammi

## Comments

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

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

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

passes.

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

I'm pretty sure your algorithm has complexity , but regardless of that your algorithm is simply wrong.

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

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

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

You may assume

• 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

• 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).

• raggarwal  commented on Nov. 24, 2014, 10:40 p.m.

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

• 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.

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

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

• 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.

• 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.

• 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++.

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

We support math here, so and .

• 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?

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

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

Thanks though!