Number of Ways to Form a Target String Given a Dictionary

Number of Ways to Form a Target String Given a Dictionary

What is this problem about?

The Number of Ways to Form a Target String Given a Dictionary problem gives you a list of equal-length words and a target string. Form the target by using characters at the same column positions across words, using each column position at most once (left-to-right). Count the number of ways modulo 10^9+7. This hard coding problem uses 2D DP with precomputed character frequencies per column.

Why is this asked in interviews?

Meta, Amazon, Snowflake, and Google ask this because it requires precomputing "how many words have character c at column j" and then applying DP over (target_position, word_column) states. The array, string, and dynamic programming interview pattern is fully exercised with a clean 2D DP formulation.

Algorithmic pattern used

Precompute column character counts + 2D DP. For each column j, precompute freq[j][c] = number of words with character c at column j. dp[i][j] = ways to form target[0..i-1] using columns 0..j-1. Transition: either skip column j (dp[i][j+1] += dp[i][j]) or use column j to form target[i] (dp[i+1][j+1] += dp[i][j] * freq[j][target[i]]). Answer: dp[target_len][word_len].

Example explanation

words=["acca","bbbb","caca"], target="aba". Column frequencies: col0={a:2,b:1}, col1={c:1,b:2}, col2={c:2,b:0,a:1}, col3={a:2,b:1}. dp[0][0]=1. Target char 'a': use col0→dp[1][1]+=12=2. Use col1→dp[1][2]+=10=0. etc. Continue for all target chars and columns. Final answer = dp[3][4].

Common mistakes candidates make

• Not precomputing column character frequencies (too slow to compute per DP state).
• Incorrect DP transition (skipping column vs using column must be separated).
• Off-by-one in DP indices (dp dimensions should be (target_len+1) × (word_len+1)).
• Not applying modular arithmetic at each multiplication.

Interview preparation tip

This problem is a variant of string matching DP where "available characters" change per position. The precomputed frequency table is the key optimization — it converts an O(mnL) problem to O(m*n). Practice similar "form a string by selecting characters from a grid" problems. The skip/use transition pattern is standard for selection DPs where you can choose to take or skip each column.