Find the number of distinct consecutive 2-letter substrings of the string S.
Explanation:
Solution for the subtask 1 (35 points):
If |S| = 2, then there is only one possible substring - the string S. So, the answer is 1.
If |S| = 3, then if all letters in the string are the same, then the answer is 1, otherwise there are 2 distinct consecutive 2-letter substrings, so, the answer is then 2.
Solution for all subtasks:
Consider a boolean array A[][] of $26$x$ 26$ elements.
Let A[i,j] be true if there is a substring of S with first letter - the ith Latin alphabet letter and the second letter - the jth Latin alphabet letter.
Initially all elements of A[][] are false.
Let’s iterate through the symbols of the string S and set true all elements of A for the corresponding substrings. Note, that S is 1-indexed in the given pseudocode.
The pseudocode for the same follows:
For k := 2 to |S|
A[S[k-1], S[k]] = true;
The last step is to iterate through the array A and calculate the number of elements A[i,j] such that A[i,j] is true.
Instead of using Set or the method given in editorial I stored all the contiguos character elements of length 2 in a 2-D character array and sorted that array using quicksort. Complexity-(O(t*N(logN))
Result-SIGSEGV
Reason-?
@ceilks declaring temp globally removed SIGSEGV but got TLE on last subtask.
REASONS?
The upper limit on the no. of test cases is 100 and quicksort is implemented in NlogN it should have passed in 1s but it didnt.
If I stick to this method can u suggest any optimised version of quicksort here(may be by chosing different pivot).
I agree with @ashdr_gon and @ arun_1713.
Using a set is the easiest solution and fast enough. Seems many people don’t know about the power of the STL.