Блог пользователя Mikemirzyanov1

Lexicographically largest substring of a string
Автор Mikemirzyanov1, история, 5 лет назад, По-английски

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.

[Solution](https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/363662/Short-python-code-O(n)-time-and-O(1)-space-with-proof-and-visualization)

I found this link on Leetcode but cannot understand it.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить