Let $a_i,b_i$ be vectors in $\mathbb{Z}^n$ expressing the number of letters of each type in $A_i,B_i$. If $k < n$ then we can find some non-zero integer vector $v$ (with no common divisor) which is orthogonal to all $a_i - b_i$. That means that the inner product with $v$ is invariant under the substitutions $A_i \leftrightarrow B_i$.
Now compute the inner product of $v$ with the histograms of all words of length at most $100$, and choose some number $M$ not appearing in this set of inner products. Construct some word $w$ with histogram whose inner product with $v$ is $M$ (here we use the fact that $v$ has no common divisor). The word $w$ cannot be reduced to $100$ letters or less.
Note that we can always find such a $w$ which is a power of a single character. So the intuition behind the earlier answer was correct.