The Edit Distance to k-Subsequence Universality

A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. The word w with alph(w)=Sigma is called k-subsequence universal if the set of subsequences of length k of w contains all possible words of length k over Sigma. We propose a series of efficient algorithms computing the minimal number of edit operations (insertion, deletion, substitution) one needs to apply to a given word in order to reach the set of k-subsequence universal words.