Representing a sequence as a vector of k-mer counts turns variable-length biological
strings into fixed-length numeric features — the foundation of alignment-free sequence comparison,
metagenomic binning, and most machine-learning approaches to genomics. The lexicographic ordering
matters because it lets two sequences be compared position by position without needing to store the
k-mer strings themselves.
Statement
Given a DNA sequence and an integer k, produce the frequency array: the count of
every possible k-mer over the alphabet {A, C, G, T}, listed in lexicographic order.
There are exactly 4^k possible k-mers. For k = 2 the lexicographic order is
AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT.
Print the 4^k counts on a single line, separated by single spaces. Overlapping occurrences count
separately.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
s
line 1
|
str |
The DNA sequence
1 <= len(s) <= 1000, uppercase A, C, G, T only
|
k
line 2
|
int |
The k-mer length
1 <= k <= 5
|
These variables are already read for you in the starter code on the right.
Output
str 4^k space-separated counts in lexicographic k-mer order, on one line
Sample Cases
ACGTACGT
2
0 2 0 0 0 0 2 0 0 0 0 2 1 0 0 0AAAA
1
4 0 0 0Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= length(s) <= 10001 <= k <= 5kmay exceedlength(s), in which case every count is zero- Overlapping k-mers are counted separately
Further Reading
itertools.product("ACGT", repeat=k)generates the k-mers already in lexicographic order.- Count with a dictionary first, then look each k-mer up — this is
O(n)rather thanO(4^k * n). - If
k > len(s)there are no windows at all, so print4^kzeros.