HardArrayStringDynamic ProgrammingUpdated Sep 2026

1639. Number of Ways to Form a Target String Given a Dictionary

Asked at Uber

Difficulty

Hard

Time

O(N * L + M * L)

Space

O(M + 26 * L)

Pattern

Array

Companies

1

Problem

You get a list of strings called words. All of them have the same length, so you can think of them as rows of a table. You also get a string called target.

You must build target from left to right, one character at a time. To place the i-th character of target, you pick some column k and some word j where words[j][k] equals target[i]. After you use column k, every column with index less than or equal to k becomes unusable — for all words. So the columns you pick must strictly increase as you move through target.

You may take several characters from the same word, as long as the column rule holds. Count the number of ways to build target. Because the count can be huge, return it modulo 10^9 + 7.

Pick one character per target letter, columns must increase

words0123012accabbbbcacaOne valid way: 'a' from row 0 col 0, 'b' from row 1col 1, 'a' from row 0 col 3.targetaba012The target letters must be filled in this order, usingstrictly increasing columns.
Each target letter is matched to a column, and the chosen columns must strictly increase from left to right.

Constraints

  • ●1 <= words.length <= 1000
  • ●1 <= words[i].length <= 1000
  • ●All strings in words have the same length.
  • ●1 <= target.length <= 1000
  • ●words[i] and target contain only lowercase English letters.

Examples

Example 1
Inputwords = ["acca","bbbb","caca"], target = "aba"
Output6
WhyColumn 0 has two 'a's (from "acca" and "caca"), column 1 has two 'b's (both from "bbbb"), and column 3 has two 'a's (from "acca" and "caca"). Choosing one 'a' from column 0, one 'b' from column 1, then one 'a' from column 3 gives 2 × 2 × 2 = 8 combinations, but two of them reuse the same word at the
Example 2
Inputwords = ["abba","baab"], target = "bab"
Output4
WhyThe 'b' for target[0] must come from column 0 or column 1, the 'a' for target[1] from a later column, and the final 'b' from an even later column. Counting the valid increasing-column choices gives 4 ways.

Asked At

1 companies
CompanyDifficulty
UberHardView all Uber questions →

How to Think About It

1

Count frequency of each character in each column of the dictionary

2

DP[i][j] = ways to form target[0..i] using first j columns

3

Base case: DP[-1][j] = 1 for all j (empty target has one way)

4

Transition: either skip column j (DP[i][j-1]) or use it (DP[i-1][j-1] * freq[target[i]][j])

5

Space optimize by rolling over columns since transitions only look at j-1

Optimal Approach

Precompute freq[c][j] = count of character c in column j across all words. Use DP where dp[i][j] represents ways to form target[0..i] using first j columns. For each state, either skip column j (carry dp[i][j-1] forward) or use it to contribute target[i] (add dp[i-1][j-1] * freq[target[i]][j]). Space optimize with a 1D array over columns.

DP over columns, one target prefix at a time

freq0123abc200202001020freq[c][j] = how many words have character c in columnj.dp10000123Start: dp[0] = 1 (empty prefix), all other entries 0.dp after all columns12260123After processing every column, dp[3] = 6 is theanswer.dp[i+1] += dp[i] * freq[target[i]][j]skip column j: dp stays the same
dp[i] counts ways to build the first i letters of target using the columns seen so far.
ComplexityTime O(N * L + M * L)Space O(M + 26 * L)N is the number of words, L is the word length, and M is the target length; building the column frequency table costs O(N * L) and the DP loop costs O(M * L).

What Trips People Up in Real Interviews

1

Clarify: you pick at most one character per column from all words combined

2

Key insight: columns are independent — each column contributes a character or nothing

3

Precompute character frequencies per column to avoid recomputation

4

Watch for overflow — use modulo at every addition/multiplication

5

Edge case: if target length exceeds word length, answer is 0

Solution Code

O(N * L + M * L) time
class Solution:
    def numWays(self, words: list[str], target: str) -> int:
        MOD = 10**9 + 7
        m, n = len(target), len(words[0])
        freq = [[0] * n for _ in range(26)]
        for word in words:
            for j, ch in enumerate(word):
                freq[ord(ch) - ord('a')][j] += 1
        dp = [0] * (m + 1)
        dp[0] = 1
        for j in range(n):
            for i in range(m - 1, -1, -1):
                dp[i + 1] = (dp[i + 1] + dp[i] * freq[ord(target[i]) - ord('a')][j]) % MOD
        return dp[m]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Ways to Form a Target String Given a Dictionary problem?

Given a dictionary of words and a target string, count the number of ways to form the target by picking exactly one character from each word in order across all words. Characters are picked column by column (all words contribute one character per column), and you can skip picking a character from any word. Return the count modulo 10^9+7.

How do you solve Number of Ways to Form a Target String Given a Dictionary?

The optimal approach runs in O(N * L + M * L) time and O(M + 26 * L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Ways to Form a Target String Given a Dictionary?

Number of Ways to Form a Target String Given a Dictionary is asked at Uber. It is a hard difficulty problem.

What are common mistakes on Number of Ways to Form a Target String Given a Dictionary?
  • Clarify: you pick at most one character per column from all words combined
  • Key insight: columns are independent — each column contributes a character or nothing
  • Precompute character frequencies per column to avoid recomputation
  • Watch for overflow — use modulo at every addition/multiplication
  • Edge case: if target length exceeds word length, answer is 0