LeetCode 1639 - Number of Ways to Form a Target String Given a Dictionary

The problem gives us a list of strings called words, where every string has the same length, and another string called target. We need to count how many different ways we can build target by selecting characters from the columns of words.

leetcodehardarraystringdynamic-programming

LeetCode Problem 1639

Difficulty: 🔴 Hard
Topics: Array, String, Dynamic Programming

Solution

Problem Understanding

The problem gives us a list of strings called words, where every string has the same length, and another string called target. We need to count how many different ways we can build target by selecting characters from the columns of words.

The important restriction is that we build target from left to right, and once we use a column index k, every column <= k becomes permanently unavailable across all strings. This means the chosen column indices must be strictly increasing.

For example, suppose we choose column 2 to build target[0]. Then the next character of the target can only come from columns 3, 4, and so on. We are not choosing entire words, we are choosing columns, and at each column we may use any word that contains the needed character there.

This changes the problem from a simple string matching task into a combinatorial dynamic programming problem.

The input constraints are large:

  • Up to 1000 words
  • Each word length up to 1000
  • Target length up to 1000

A naive recursive search would explode exponentially because every target character may have many valid column choices. We therefore need a highly optimized solution.

A few observations immediately stand out:

  • Since all words have the same length, we can think column by column.
  • The order of columns matters.
  • Multiple words may contribute the same character in a column.
  • We only care about character frequencies per column, not the exact identity of each word.

Important edge cases include:

  • The target being longer than the word length, which makes the answer automatically 0.
  • Columns that do not contain required characters.
  • Large counts that require modulo arithmetic.
  • Repeated characters in the target, which can create many overlapping subproblems.

Approaches

Brute Force Approach

A brute force solution would recursively try every possible column for every character in the target.

For each target character:

  1. Iterate through all remaining columns.
  2. Check every word to see whether the column contains the needed character.
  3. Recursively continue building the rest of the target.

This approach is correct because it explores every valid sequence of increasing column indices. However, it is far too slow.

If there are m columns and target length t, the number of possible increasing column sequences alone is roughly combinatorial, close to C(m, t). Additionally, each step scans all words.

The runtime becomes exponential and cannot handle the constraint sizes.

Key Insight

The key observation is that the actual identity of the word does not matter. What matters is:

For each column, how many words contain each character.

Suppose column 5 contains the letter 'a' in 7 different words. If we want to place 'a' at this step, then this column contributes 7 possible choices.

This lets us preprocess frequency counts:

count[column][character] = number of words having that character in that column

Then the problem becomes:

  • Process columns from left to right.
  • Decide whether to use the current column for the next target character.
  • Use dynamic programming to count ways efficiently.

This transforms an exponential search into polynomial time.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^m × n) approximately O(t) recursion Explores all column combinations
Optimal Dynamic Programming O(n × m + m × t) O(m × 26 + t) Uses column character frequencies and DP

Where:

  • n = len(words)
  • m = len(words[0])
  • t = len(target)

Algorithm Walkthrough

Step 1: Precompute character frequencies per column

We create a 2D array where:

freq[col][char]

stores how many words contain char at column col.

For example:

words = ["acca","bbbb","caca"]

Column 0 contains:

a, b, c

So:

freq[0]['a'] = 1
freq[0]['b'] = 1
freq[0]['c'] = 1

This preprocessing allows us to instantly know how many choices exist for a target character at a given column.

Step 2: Define the DP state

We define:

dp[i]

as the number of ways to form the first i characters of the target.

Initially:

dp[0] = 1

because there is exactly one way to form an empty string.

Step 3: Process columns from left to right

For each column:

  • We may choose to use it for some target character.
  • Or we may skip it.

To avoid overwriting states too early, we iterate target indices backward.

Suppose current column contributes character 'a' three times.

If:

target[j] == 'a'

then:

dp[j + 1] += dp[j] * 3

This means:

  • Every way to build the first j characters
  • Can extend into a way to build the first j + 1
  • Using any of the three available 'a' characters in this column.

Step 4: Use modulo arithmetic

The number of combinations can become enormous, so every update is computed modulo:

10^9 + 7

Step 5: Return the final answer

After processing all columns:

dp[len(target)]

contains the total number of ways to form the entire target.

Why it works

The algorithm maintains the invariant that after processing column c, dp[i] stores the number of ways to build the first i characters of the target using only columns 0...c.

Each column is processed exactly once, and backward iteration ensures that a column cannot be reused multiple times for different target positions. Since every valid construction corresponds to a unique sequence of increasing columns, the DP counts every valid solution exactly once.

Python Solution

from typing import List

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 10**9 + 7
        
        word_length = len(words[0])
        target_length = len(target)
        
        if target_length > word_length:
            return 0
        
        # freq[col][char_index]
        freq = [[0] * 26 for _ in range(word_length)]
        
        for word in words:
            for col, ch in enumerate(word):
                freq[col][ord(ch) - ord('a')] += 1
        
        # dp[i] = number of ways to form first i characters
        dp = [0] * (target_length + 1)
        dp[0] = 1
        
        for col in range(word_length):
            # Traverse backwards to avoid reusing same column
            for i in range(target_length - 1, -1, -1):
                target_char_index = ord(target[i]) - ord('a')
                
                char_count = freq[col][target_char_index]
                
                if char_count > 0:
                    dp[i + 1] = (
                        dp[i + 1] + dp[i] * char_count
                    ) % MOD
        
        return dp[target_length]

The implementation begins by checking whether the target is longer than the available column count. If it is, forming the target is impossible.

Next, the solution builds the frequency table. Instead of repeatedly scanning all words during DP transitions, each column stores how many times each character appears.

The dynamic programming array is then initialized. dp[0] = 1 represents the empty prefix.

For every column, we iterate backward through the target indices. Backward traversal is essential because it prevents using the same column multiple times in one iteration.

Each update:

dp[i + 1] += dp[i] * char_count

means:

  • There are dp[i] ways to form the current prefix.
  • The current column offers char_count ways to extend it.

Finally, dp[target_length] contains the total number of valid constructions.

Go Solution

func numWays(words []string, target string) int {
	const MOD int = 1_000_000_007

	wordLength := len(words[0])
	targetLength := len(target)

	if targetLength > wordLength {
		return 0
	}

	// freq[col][char]
	freq := make([][]int, wordLength)
	for i := 0; i < wordLength; i++ {
		freq[i] = make([]int, 26)
	}

	for _, word := range words {
		for col, ch := range word {
			freq[col][ch-'a']++
		}
	}

	dp := make([]int, targetLength+1)
	dp[0] = 1

	for col := 0; col < wordLength; col++ {
		for i := targetLength - 1; i >= 0; i-- {
			charIndex := target[i] - 'a'
			charCount := freq[col][charIndex]

			if charCount > 0 {
				dp[i+1] = (dp[i+1] + dp[i]*charCount) % MOD
			}
		}
	}

	return dp[targetLength]
}

The Go implementation follows the same logic as the Python version.

One important difference is integer handling. Since intermediate multiplication values may become large, modulo arithmetic is applied immediately after every update.

Go slices are initialized explicitly, unlike Python lists which can be created with multiplication syntax.

The reverse traversal logic remains exactly the same because it is critical for correctness.

Worked Examples

Example 1

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

Frequency Table

Column a b c
0 1 1 1
1 1 1 1
2 0 1 2
3 2 1 0

DP Initialization

dp = [1, 0, 0, 0]

Meaning:

  • dp[0] = 1, empty string

Process Column 0

Need target characters in reverse:

i = 2, target[2] = 'a'

freq[0]['a'] = 1
dp[3] += dp[2] * 1 = 0

i = 1, target[1] = 'b'

freq[0]['b'] = 1
dp[2] += dp[1] * 1 = 0

i = 0, target[0] = 'a'

freq[0]['a'] = 1
dp[1] += dp[0] * 1

Now:

dp = [1, 1, 0, 0]

Process Column 1

After updates:

dp = [1, 2, 1, 0]

Process Column 2

After updates:

dp = [1, 2, 3, 0]

Process Column 3

After updates:

dp = [1, 4, 5, 6]

Final answer:

6

Complexity Analysis

Measure Complexity Explanation
Time O(n × m + m × t) Frequency preprocessing plus DP transitions
Space O(m × 26 + t) Frequency table and DP array

Where:

  • n is the number of words
  • m is the word length
  • t is the target length

The preprocessing scans every character in every word exactly once, producing O(n × m) complexity.

The DP phase processes every column and every target position once, resulting in O(m × t) time.

The space usage comes from the frequency table and the one-dimensional DP array.

Test Cases

from typing import List

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        MOD = 10**9 + 7
        
        word_length = len(words[0])
        target_length = len(target)
        
        if target_length > word_length:
            return 0
        
        freq = [[0] * 26 for _ in range(word_length)]
        
        for word in words:
            for col, ch in enumerate(word):
                freq[col][ord(ch) - ord('a')] += 1
        
        dp = [0] * (target_length + 1)
        dp[0] = 1
        
        for col in range(word_length):
            for i in range(target_length - 1, -1, -1):
                char_index = ord(target[i]) - ord('a')
                count = freq[col][char_index]
                
                dp[i + 1] = (dp[i + 1] + dp[i] * count) % MOD
        
        return dp[target_length]

solution = Solution()

assert solution.numWays(
    ["acca", "bbbb", "caca"],
    "aba"
) == 6  # Provided example 1

assert solution.numWays(
    ["abba", "baab"],
    "bab"
) == 4  # Provided example 2

assert solution.numWays(
    ["abcd"],
    "abcd"
) == 1  # Exact single construction

assert solution.numWays(
    ["abcd"],
    "abcde"
) == 0  # Target longer than word length

assert solution.numWays(
    ["aaaa", "aaaa"],
    "aa"
) == 24  # Many combinations

assert solution.numWays(
    ["abc", "def"],
    "zzz"
) == 0  # Impossible target

assert solution.numWays(
    ["ab", "ab", "ab"],
    "ab"
) == 9  # Multiple identical words

assert solution.numWays(
    ["xyz"],
    "x"
) == 1  # Single character target

assert solution.numWays(
    ["aaa", "aaa", "aaa"],
    "aaa"
) == 27  # Repeated character across all columns

assert solution.numWays(
    ["bac", "bac", "bac"],
    "ac"
) == 9  # Must use increasing columns
Test Why
["acca","bbbb","caca"], "aba" Verifies official example
["abba","baab"], "bab" Verifies another official example
["abcd"], "abcd" Exact match case
["abcd"], "abcde" Target longer than columns
["aaaa","aaaa"], "aa" Large combinational count
["abc","def"], "zzz" Impossible target
["ab","ab","ab"], "ab" Duplicate words
["xyz"], "x" Smallest meaningful target
["aaa","aaa","aaa"], "aaa" Repeated character DP transitions
["bac","bac","bac"], "ac" Confirms increasing column restriction

Edge Cases

Target Longer Than Word Length

If the target length exceeds the word length, forming the target is impossible because columns must be used in strictly increasing order and each column can contribute at most one character.

A naive implementation might still attempt recursion or DP, wasting time. This solution immediately returns 0.

Missing Required Characters

Some targets may contain characters that never appear in the necessary columns.

For example:

words = ["abc", "def"]
target = "zzz"

In this case every frequency lookup becomes zero, so no DP transitions occur. The algorithm naturally leaves the final DP state at zero.

Repeated Characters Causing Double Counting

Targets such as:

target = "aaa"

can easily cause bugs if the DP updates are performed left to right.

If we updated forward, the same column could accidentally contribute multiple target positions in one iteration. The backward traversal prevents this by ensuring each column is used at most once per transition layer.

Extremely Large Answer Values

The number of combinations can become enormous because each column may contribute many valid choices.

Without modulo arithmetic, integer overflow would occur in many languages. Both implementations apply modulo 10^9 + 7 after every update, guaranteeing correctness even for the largest inputs.