= Solution
Keep 26 cached counts, updating them after a successful delegated edit. Count exactly lowercase letters; the query alphabet does not make uppercase letters the same character.
``
trait CharTrackPlugIn extends Doc {
private val counts = Array.fill[Int](26)(0)
private def lower(x: Char): Boolean = 'a' <= x && x <= 'z'
abstract override def insert(x: Char, pos: Int): Unit = {
super.insert(x, pos)
if (lower(x)) counts(x - 'a') += 1
}
abstract override def delete(pos: Int): Char = {
val x = super.delete(pos)
if (lower(x)) counts(x - 'a') -= 1
x
}
def getCount(x: Char): Int = {
assert(lower(x))
counts(x - 'a')
}
}
``
For an initially empty underlying document that stores inserted arguments unchanged, the <representation invariant> is
$$
\boxed{\mathrm{counts}(c-\texttt{'a'})=\#\{i:\mathrm{read}(i)=c\}\quad(c=\texttt{'a'},\ldots,\texttt{'z'}).}
$$
Insertion increments precisely the inserted lowercase character's count. Deletion uses the returned character, avoiding an extra indexed read and decrementing the character actually removed. Updating after `super` means a rejected edit leaves the counts unchanged. Both the added update work and `getCount` use $O(1)$ <time complexity> and fixed storage.
The `abstract override` methods implement a <stackable trait modification>: they require a concrete document implementation further along the delegation chain. The invariant above depends on subsequent layers preserving inserted characters. Part (d) deliberately composes a transforming layer that can break this assumption; that is the <transform-sensitive trait frequency counter> phenomenon.
Back to article page
