Before revision:  We note that if \ell = 1, i.e., we are trying to learn a single string , learning the distribution is equivalent to the famous trace reconstruction problem. The best known algorithms for trace reconstruction require \exp O(n^{1/3)} samples.
After revision:  We note that if \ell = 1, i.e., we are trying to learn a single string  O(n^{1/3)} samples.