Number of Ways to Form a Target String Given a Dictionary

hard dp counting

Problem

You get a dictionary words where every string has the same length, plus a string target. Build target left to right: to produce its next character you pick a matching character sitting at some column k of any word, and once column k is used, every column ≤ k of every word becomes off-limits — so the columns you pick must strictly increase.

Count how many distinct ways target can be formed, modulo 10⁹ + 7. Two ways differ if any character comes from a different (word, column) pair.

Inputwords = ["acca", "bbbb", "caca"], target = "aba"

Output6

The letters 'a', 'b', 'a' can be taken from strictly increasing columns in exactly 6 ways, e.g. 'a' from "acca" column 0, 'b' from "bbbb" column 1, 'a' from "caca" column 3.

words (comma-separated, equal lengths)

target

def num_ways(words, target):
    MOD = 10 ** 9 + 7
    m, t = len(words[0]), len(target)
    cnt = [[0] * 26 for _ in range(m)]
    for w in words:
        for k, ch in enumerate(w):
            cnt[k][ord(ch) - 97] += 1
    dp = [0] * (t + 1)
    dp[0] = 1  # one way to form the empty prefix
    for k in range(m):
        for i in range(min(t, k + 1), 0, -1):
            c = ord(target[i - 1]) - 97
            dp[i] = (dp[i] + dp[i - 1] * cnt[k][c]) % MOD
    return dp[t]

function numWays(words, target) {
  const MOD = 1000000007;
  const m = words[0].length, t = target.length;
  const cnt = Array.from({ length: m }, () => new Array(26).fill(0));
  for (const w of words)
    for (let k = 0; k < m; k++) cnt[k][w.charCodeAt(k) - 97]++;
  const dp = new Array(t + 1).fill(0);
  dp[0] = 1; // one way to form the empty prefix
  for (let k = 0; k < m; k++)
    for (let i = Math.min(t, k + 1); i >= 1; i--) {
      const c = target.charCodeAt(i - 1) - 97;
      dp[i] = (dp[i] + dp[i - 1] * cnt[k][c]) % MOD;
    }
  return dp[t];
}

int numWays(String[] words, String target) {
    final int MOD = 1000000007;
    int m = words[0].length(), t = target.length();
    int[][] cnt = new int[m][26];
    for (String w : words)
        for (int k = 0; k < m; k++) cnt[k][w.charAt(k) - 'a']++;
    long[] dp = new long[t + 1];
    dp[0] = 1; // one way to form the empty prefix
    for (int k = 0; k < m; k++)
        for (int i = Math.min(t, k + 1); i >= 1; i--) {
            int c = target.charAt(i - 1) - 'a';
            dp[i] = (dp[i] + dp[i - 1] * cnt[k][c]) % MOD;
        }
    return (int) dp[t];
}

int numWays(vector<string>& words, string target) {
    const long long MOD = 1000000007;
    int m = words[0].size(), t = target.size();
    vector<vector<int>> cnt(m, vector<int>(26, 0));
    for (auto& w : words)
        for (int k = 0; k < m; k++) cnt[k][w[k] - 'a']++;
    vector<long long> dp(t + 1, 0);
    dp[0] = 1; // one way to form the empty prefix
    for (int k = 0; k < m; k++)
        for (int i = min(t, k + 1); i >= 1; i--) {
            int c = target[i - 1] - 'a';
            dp[i] = (dp[i] + dp[i - 1] * cnt[k][c]) % MOD;
        }
    return (int) dp[t];
}

Explanation

The key insight: because the chosen columns must strictly increase, it never matters which word a character came from — only which column. So we compress the whole dictionary into a table cnt[k][c] = how many words carry letter c in column k. Picking letter c at column k then contributes a factor of cnt[k][c] choices.

Now it becomes a counting DP. Let dp[i] = the number of ways to form the first i characters of target using only the columns processed so far, with dp[0] = 1 for the empty prefix. We sweep columns left to right. Column k can either be skipped (dp unchanged) or used to supply the character target[i-1], adding dp[i-1] · cnt[k][target[i-1]] new ways to dp[i].

We iterate i downward inside each column — the classic 0/1-knapsack trick — so a single column can serve at most one target position. Iterating upward would let the same column match two consecutive target characters, which the rules forbid. The bound i ≤ k + 1 just skips states that cannot exist yet (you cannot match 3 characters using only 2 columns).

Walking the default example words = ["acca", "bbbb", "caca"], target = "aba": column 0 holds one 'a', so dp[1] = 1. Column 1 adds another 'a' (dp[1] = 2) and one 'b' after an 'a' (dp[2] = 1). Column 2 has one more 'b', pushing dp[2] to 3. Column 3 holds two 'a's, so dp[3] += 3 · 2 = 6 — the answer.

Complexity: building cnt touches every character once, O(n · m) for n words of length m. The DP does at most t updates per column, O(m · t), each a constant-time multiply-add under the modulus. Space is the count table plus the 1-D dp array.

Time: O(m·(n + t)) Space: O(26·m + t)