| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
Hi can someone share the approach to find lexicographically largest substring in a string?
I know the answer will always be one of the suffixes but cannot find a way to analyze those suffixes efficiently.
Constraints |S| < 1e5
I need an O(n) approach or O(nlogn) without suffix array.
Any ideas are welcome.
I found this link on Leetcode but cannot understand it.
If a substring is the largest lexicographically, then it must start with the largest element from the string.
Observation: If you add elements to the end of a string it makes it larger lexicographically.
Therefore, the answer shold be the substring from the first occurence of the biggest character to the end of the string.
test case :- aazaaaazz
your output ?
Test case ;- zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
What he is proposing is probably O(n*n) I think.
or zz only?
you can solve it by using hash + binary search, O(n*log(n)), because you need to find maximum of n strings(suffixes), so you can do n comparisons(by using binary search you can find maximum equal prefix, and then compare next letter)
One of the solutions, not the optimal and not easy one is to just create suffix array and take last value as position in suffix array