Code Implementation

MOD = 10 ** 9 + 7

class Solution:
    def numWays(self, words, target):
        from collections import Counter
        m, n = len(words[0]), len(target)
        # Precompute frequency of each character at each position
        freq = [Counter() for _ in range(m)]
        for word in words:
            for i, c in enumerate(word):
                freq[i][c] += 1

        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(m):
            for j in range(n-1, -1, -1):
                c = target[j]
                dp[j+1] = (dp[j+1] + dp[j] * freq[i][c]) % MOD

        return dp[n]
      

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        const int MOD = 1e9 + 7;
        int m = words[0].size(), n = target.size();
        vector<vector<int>> freq(m, vector<int>(26, 0));
        for (auto& word : words) {
            for (int i = 0; i < m; ++i) {
                freq[i][word[i] - 'a']++;
            }
        }
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                int c = target[j] - 'a';
                dp[j + 1] = (dp[j + 1] + dp[j] * freq[i][c]) % MOD;
            }
        }
        return dp[n];
    }
};
      

import java.util.*;

class Solution {
    public int numWays(String[] words, String target) {
        int MOD = 1000000007;
        int m = words[0].length(), n = target.length();
        int[][] freq = new int[m][26];
        for (String word : words) {
            for (int i = 0; i < m; ++i) {
                freq[i][word.charAt(i) - 'a']++;
            }
        }
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                char c = target.charAt(j);
                dp[j + 1] = (dp[j + 1] + dp[j] * freq[i][c - 'a']) % MOD;
            }
        }
        return (int)dp[n];
    }
}
      

var numWays = function(words, target) {
    const MOD = 1e9 + 7;
    const m = words[0].length, n = target.length;
    // Precompute frequencies
    const freq = Array.from({length: m}, () => Array(26).fill(0));
    for (const word of words) {
        for (let i = 0; i < m; ++i) {
            freq[i][word.charCodeAt(i) - 97]++;
        }
    }
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < m; ++i) {
        for (let j = n - 1; j >= 0; --j) {
            const c = target.charCodeAt(j) - 97;
            dp[j+1] = (dp[j+1] + dp[j] * freq[i][c]) % MOD;
        }
    }
    return dp[n];
};
      

Problem Description

Given a list of strings words where each string has the same length, and a target string target, you need to determine how many ways you can form target by picking one character from each column (i.e., all characters at the same index in every word) in words. For each character in target, you must pick it from a column to the right of (or at) the position of the previous character you picked (no going back to earlier columns). Every column can only be used once and you cannot reuse characters from the same column for different target positions.

• You may pick any character from any word in a given column.
• Return the total number of ways to form target modulo 10⁹ + 7.
• Constraints: All words have the same length; target is not longer than any word.

Thought Process

At first glance, you might consider a brute-force approach: for every character in target, try every possible way to pick that character from the available columns in words, recursively or via backtracking. However, this quickly becomes infeasible because the number of combinations grows exponentially with the length of words[0] and target.

To optimize, we notice two key ideas:

• Each position in target must be matched with a column in words at or after the previous character's column.
• We can precompute, for each column, how many times each letter appears. This avoids repeatedly counting possibilities.

Solution Approach

We solve the problem using dynamic programming and precomputation:

1. Precompute Frequencies:
   • For each column index in words, count how many times each letter ('a'-'z') appears across all words at that column position.
2. Dynamic Programming (DP):
   • Let dp[j] be the number of ways to form the first j characters of target using the first i columns of words.
   • Initialize dp[0] = 1 (1 way to form an empty target).
   • For each column i in words:
     • For each position j in target, from last to first (so previous dp values are not overwritten):
     • If target[j] appears in this column, add dp[j] * (frequency of target[j] in column i) to dp[j+1].
3. Result:
   • The answer is dp[target.length] after processing all columns.
   • Take the result modulo 10⁹+7 to avoid overflow.

This approach is efficient because it avoids redundant calculations and leverages the fact that the order of columns matters, but the order of words within a column does not.

Example Walkthrough

Let's walk through an example:

Input:
words = ["acca","bbbb","caca"]
target = "aba"

• Length of each word = 4, length of target = 3.
• For each column, count the frequency of each character:
  • Column 0: 'a':1, 'b':1, 'c':1
  • Column 1: 'c':2, 'b':1
  • Column 2: 'c':2, 'b':1
  • Column 3: 'a':2, 'b':1
• Initialize dp = [1, 0, 0, 0] (since target has length 3).
• For each column (from 0 to 3), and for each target position (from 2 to 0), update dp:
  • Column 0: target[0] = 'a' appears 1 time, so dp[1] += dp[0] * 1 = 1
  • Column 1: target[1] = 'b' appears 1 time, so dp[2] += dp[1] * 1 = 1
  • Column 2: target[2] = 'a' appears 0 times, so dp[3] remains 0
  • Column 3: target[2] = 'a' appears 2 times, so dp[3] += dp[2] * 2 = 2
• Final dp = [1, 1, 1, 2], so answer is 2.

There are 2 ways to form "aba" from the columns of the given words.

Time and Space Complexity

Brute-force:

• For each character in target, you could try every possible column and every possible word, leading to exponential time: O(mⁿ * k), where m = word length, n = target length, k = number of words.

• Precomputing frequencies: O(m * k) (for m columns and k words).
• DP: O(m * n) (for each column and each position in target).
• Total: O(m*k + m*n).
• Space: O(m*26) for frequency table + O(n) for DP array.

This is efficient and feasible for the given constraints.

Summary

The solution leverages dynamic programming and precomputed character frequencies to efficiently count the number of ways to form a target string from columns of multiple words. By iterating through columns and updating possible ways to form each prefix of the target, we avoid redundant work and reduce the problem from exponential to polynomial time. The approach is elegant because it turns a seemingly recursive, combinatorial challenge into a simple DP update, making it both fast and easy to implement.