SuffixArrayDiv1
SRM 630 · 2014-07-26 · by cgy4ever
SRM 630 · 2014-07-26 · by cgy4ever · Math
Problem Statement
Problem Statement
Suffix number i of a string S is the suffix that starts with the character S[i].
For example, for S="abcde" suffix 0 is "abcde" and suffix 3 is "de".
The suffix array of a string S is defined as the permutation of suffix numbers that corresponds to their lexicographic order. For example, suppose that S="abca". If we order all suffixes of S lexicographically, we get the following: "a" < "abca" < "bca" < "ca". The corresponding suffix numbers are 3, 0, 1, and 2, in this order. Thus, for this string S the suffix array would be {3, 0, 1, 2}. Note that the length of a suffix array is the same as the length of the original string.
You are given aint[] SA: the suffix array of an unknown string.
Return the smallest possible number of different characters in that string.
The suffix array of a string S is defined as the permutation of suffix numbers that corresponds to their lexicographic order. For example, suppose that S="abca". If we order all suffixes of S lexicographically, we get the following: "a" < "abca" < "bca" < "ca". The corresponding suffix numbers are 3, 0, 1, and 2, in this order. Thus, for this string S the suffix array would be {3, 0, 1, 2}. Note that the length of a suffix array is the same as the length of the original string.
You are given a
Notes
- We do not consider any specific alphabet. In particular, it is possible to have more than 26 different letters.
- For any suffix array, there is at least one string with such a suffix array, so the return value is always defined.
- The string A is smaller than a different string B in lexicographic order either if A is a prefix of B, or if there are indices where A and B differ, and for the smallest such index i we have A[i] < B[i].
Constraints
- SA will contain between 1 and 50 elements, inclusive.
- SA will be a permutation of 0 to |SA|-1, inclusive.
Examples
0)
{3,0,1,2}
Returns: 2
As we saw in the problem statement, the suffix array {3,0,1,2} corresponds to the string "abca". However, there are also other string with the same suffix array. For example, the string "xxyx" also has this property, and contains only two different characters.
1)
{3,2,1,0}
Returns: 1
One optimal string is "aaaa".
2)
{0,1,2,3}
Returns: 2
Here, one optimal string is "aaaz".
3)
{7,4,8,6,1,5,2,9,3,0}
Returns: 4
4)
{0}
Returns: 1
Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SuffixArrayDiv1 with a public method int minimalCharacters(vector<int> SA) · 121 test cases · 2 s / 256 MB per case