3335. Total Characters in String After Transformations I
Approach
Track char frequencies; each step 'z' splits to 'a'+'b'; use array rotation.
Key Techniques
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
// Approach: Track char frequencies; each step 'z' splits to 'a'+'b'; use array rotation.
// Time: O(26 * t) Space: O(26)
public class Solution
{
public int LengthAfterTransformations(string s, int t)
{
const int MOD = 1_000_000_007;
int[] count = new int[26];
foreach (char c in s)
count[c - 'a']++;
while (t-- > 0)
{
int[] newCount = new int[26];
// 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
for (int i = 0; i < 25; i++)
newCount[i + 1] = count[i];
// 'z' -> 'ab'
newCount[0] = count[25];
newCount[1] = (newCount[1] + count[25]) % MOD;
count = newCount;
}
return count.Aggregate(0, (a, b) => (a + b) % MOD);
}
}