Lexicographically Least Substring (Hard)

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.8s

Memory limit: 256M

Problem type

Brute Force Practice 2 — Hard Version

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

Input Specification

The first line will have the string.

The second line will have $K$ $K$ .

Output Specification

Print the lexicographically least substring of length at least $K$ $K$ .

Sample Input

Copy

iloveprogramming
4

Sample Output

Copy

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$ $K$ is larger than the given string.

7

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

You may assume $K \le |S|$ $K \leq | 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)$ $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)$ $O (N^{2} \log N)$ . There are $\mathcal{O}(N)$ $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!