SuffixArrayDiv2
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.
In this problem, we will only consider strings of lowercase English letters ('a'-'z'). You are given aString s.
We are interested in a string t that is lexicographically smaller than s but has exactly the same suffix array.
Return "Exists" if at least one such string t exists, and "Does not exist" otherwise.
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.
In this problem, we will only consider strings of lowercase English letters ('a'-'z'). You are given a
Notes
- Given two different strings A and B of the same length, A is lexicographically smaller than B if we have A[i] < B[i] for the smallest i such that A[i] and B[i] differ.
Constraints
- s will contain between 1 and 50 elements, inclusive.
- Each element in s will be a lowercase letter ('a'-'z').
Examples
0)
"abca" Returns: "Exists"
For example, "aaqa" < "abca" but their suffix arrays are the same.
1)
"bbbb" Returns: "Exists"
Obviously, one of the strings smaller than "bbbb" with the same suffix array is "aaaa".
2)
"aaaa" Returns: "Does not exist"
The string "aaaa" is already the lexicographically smallest 4-letter string.
3)
"examplesareveryweakthinktwicebeforesubmit" Returns: "Exists"
4)
"b" Returns: "Exists"
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SuffixArrayDiv2 with a public method string smallerOne(string s) · 113 test cases · 2 s / 256 MB per case