## Lexicographically Least Substring (Hard)

View as PDF##### 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

passes.

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

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

You may assume

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

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

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

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

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

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.

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.

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

We support math here, so and .

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?

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

Thanks though!