0373HardStringDynamic Programming

Ways to Spell the Motif

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

trace and motif are strings of English letters. Upper case and lower case are different letters throughout.

A pick is a set of positions in trace, read in increasing order, whose letters spell motif exactly. Two picks count as different when their position sets differ, even when the letters they read off are identical.

Return how many picks trace admits for motif.

Examples

Example 1

Input: trace = "AbAb", motif = "Ab"
Output: 3

The picks are positions (0,1), (0,3) and (2,3). Each reads A then b.

Example 2

Input: trace = "aaaa", motif = "aa"
Output: 6

Any two of the four positions spell the motif, and there are six such pairs.

Example 3

Input: trace = "aA", motif = "a"
Output: 1

Only position 0 holds a lower-case a; position 1 holds a different letter because case matters.

Example 4

Input: trace = "ab", motif = "abc"
Output: 0

The motif needs three positions and the trace only offers two, so no pick exists.

Constraints

1 <= trace.length, motif.length <= 1000
trace and motif consist of English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_distinct(trace: str, motif: str) -> int:

Java

public int numDistinct(String trace, String motif)

The intended approach

Time O(len(trace) * len(motif))Space O(len(motif))

Keep one running count per motif prefix: entry j says how many picks so far spell the first j letters of the motif, starting with one empty pick for the prefix of length zero. For each letter of the trace, every prefix ending in that letter can be extended by this position, so entry j grows by entry j - 1. Running the motif index downwards means entry j - 1 is still the value from before this trace letter, which keeps one position from being counted twice in the same pick.

Pythonentry point: num_distinct

def num_distinct(trace, motif):
    # counts[j] = number of picks that already spell the first j letters of the
    # motif. Sweeping the motif downwards inside the trace loop stops a single
    # trace position from being used twice in one pick.
    # Time O(len(trace) * len(motif)), space O(len(motif)).
    m = len(motif)
    counts = [0] * (m + 1)
    counts[0] = 1
    for ch in trace:
        for j in range(m, 0, -1):
            if motif[j - 1] == ch:
                counts[j] += counts[j - 1]
    return counts[m]

The obvious version

Enumerate every combination of positions in the trace whose size matches the motif length and count the ones whose letters line up with the motif position by position.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

from itertools import combinations


def bf_num_distinct(trace, motif):
    m = len(motif)
    if m > len(trace):
        return 0
    found = 0
    for picked in combinations(range(len(trace)), m):
        if all(trace[picked[k]] == motif[k] for k in range(m)):
            found += 1
    return found

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in