Mikemirzyanov1's blog

Lexicographically largest substring of a string
By Mikemirzyanov1, history, 5 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like 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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply