For k∈ℤ+, define Σk as the set of integers {0,1,…,k−1}. Given an integer n and a string t of length m≥n over Σk, we count the number of times that each one of the kn distinct strings of length n over Σk occurs as a subsequence of t. Our algorithm makes only one scan of t and solves the problem in time complexity mkn−1 and space complexity m+kn. These are very close to best possible.