3335: Total-Characters-in-String-After-Transformations-I
Medium
table of contents
General Algorithm:
I basically realised that there was a pattern for this question.
Given a frequency array letterFrequency, with the frequency
of a being stored at index 0, b
at index 1, c at index 2 etc, as
an example, we have:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]Then after 1 transformation, the frequency array is like a circular queue with the value at the last index now appearing at the beginning:
[26, 27, 2, 3, 4, 5, 6, 7, 8, 9, ..., 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]Notice, however that after each transformation, that you always add
the value that you shifted to the immediate next value
(in this case, it is adding 26 to 1 to get
27).
After another transformation, you will see something similar occurring:
[25, 51, 27, 2, 3, 4, 5, 6, 7, 8, ..., 15, 16, 17, 18, 19, 20, 21, 22, 23, 24](where you add 25 to 26 to get
51).
Therefore, you can summarise each transformation as:
Further Optimisations:
However, we can further optimise this algorithm by not shifting any elements anymore. Since we only care about the character count in the string AFTER transformation, instead of keeping the index of each letter constant and shifting the frequencys, we could keep the frequencys in the same location, and instead shift the INDEX of each letter.
An example, using letters to represent their respective index positions:
[a, b, c, d, e, f, g, h, i, j, ..., q, r, s, t, u, v, w, x, y, z]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]After 1 transformation, originally we have:
[a, b, c, d, e, f, g, h, i, j, ..., q, r, s, t, u, v, w, x, y, z]
[26, 27, 2, 3, 4, 5, 6, 7, 8, 9, ..., 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]however, if we left shift the index of each letter, we have:
[ b, c, d, e, f, g, h, i, j, k, ..., r, s, t, u, v, w, x, y, z, a]
[27, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]After another transformation, we can see the same pattern occurring:
[ a, b, c, d, e, f, g, h, i, j, ..., q, r, s, t, u, v, w, x, y, z]
[25, 51, 27, 2, 3, 4, 5, 6, 7, 8, ..., 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]with left shifting the index of each letter, we get:
[ c, d, e, f, g, h, i, j, k, ..., r, s, t, u, v, w, x, y, z, a, b]
[27, 2, 3, 4, 5, 6, 7, 8, 9, ..., 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 51]We can imitate this just by keeping a pointer variable
that tracks the index of z. On every
transformation, we make sure
pointer = (26 + pointer - 1) % 26; gets executed
(shifts the pointer left on every transformation, making it
wrap once it reaches the left most element).
code
class Solution {
static const int MOD = 1e9+7;
public:
int lengthAfterTransformations(string s, int t) {
long letterFrequency[26] = {0};
for (char& c : s) {
++letterFrequency[c-'a'];
}
int modulus = 25;
for (int i = 0; i < t; ++i) {
letterFrequency[(modulus+1)%26] = letterFrequency[(modulus+1)%26] + letterFrequency[modulus] % MOD;
modulus = (26 + modulus-1) % 26;
}
long sum = 0;
for (long & frequency : letterFrequency) {
sum = (sum + frequency) % MOD;
}
return (int)sum;
}
};