1089. Suffix Order
A search engine indexes a lowercase text s by sorting all of its suffixes. The suffix that starts at position i is the string s[i], s[i+1], ..., s[n-1], where n is the length of s. Suffixes are compared in ordinary dictionary order, and a suffix that is a proper prefix of another one counts as smaller.
Return an array of length n that lists the starting positions of the suffixes in increasing dictionary order. Since no two suffixes have the same length, the order is always unique. For example, for "cab" the suffixes are "cab", "ab" and "b", so the answer is [1, 2, 0].
Sorting the suffixes as separate strings is too slow and memory-hungry when s is long.
Example 1
- Input:
- s = "banana"
- Output:
- [5,3,1,0,4,2]
- Explanation:
Sorted, the suffixes are "a" (5), "ana" (3), "anana" (1), "banana" (0), "na" (4) and "nana" (2); a suffix that is a prefix of another one comes first.
Example 2
- Input:
- s = "abc"
- Output:
- [0,1,2]
- Explanation:
Each suffix starts with a later letter than the previous one, so the order is simply the positions 0, 1, 2.
Example 3
- Input:
- s = "cba"
- Output:
- [2,1,0]
- Explanation:
The suffix "a" is the smallest, then "ba", then "cba", so the starting positions come out reversed.
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)