We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Form a Target String Given a Dictionary

Number: 1744

Difficulty: Hard

Paid? No

Companies: Snowflake, Google, Meta, Meesho, Amazon, Apple, Dunzo

Problem Description

Given a list of words (all of the same length) and a target string, determine the number of ways to form the target string by selecting characters from the words under these rules:

  • The target is formed from left to right.
  • To form the i‑th character of the target, you can choose the k‑th character from any word if it matches target[i].
  • Once you use the k‑th character from any word, all characters at index <= k in every word become unusable in future steps. Return the number of ways to form target modulo 10^9 + 7.

Key Insights

  • Precompute the frequency of each character for every column across all words.
  • Use dynamic programming where dp[i] represents the number of ways to form the first i characters of target using processed columns.
  • Update dp in reverse order for each column to avoid interfering with the current state.
  • Multiply the number of ways by the frequency of the target character available in the current column.
  • The result is found in dp[target.length] and must be modulo 10^9 + 7.

Space and Time Complexity

Time Complexity: O(m * n) where m is the length of the words and n is the length of the target. Space Complexity: O(m + n) due to the frequency table for each column and dp array of length n+1.

Solution

We first build a frequency list where for each column in the words, we record how many times each letter appears. Then, using dynamic programming, we initialize dp[0] = 1 (an empty target can always be formed). For each column (left to right), we update the dp array in reverse order. For each character in the target (from end to beginning), we add the number of ways by multiplying the existing dp value with the frequency of the corresponding target character in the current column (if available). Finally, we return dp[target.length] modulo 10^9 + 7.

Code Solutions

# Define the function to compute number of ways.
def numWays(words, target):
    mod = 10**9 + 7
    word_len = len(words[0])
    target_len = len(target)
    
    # Precompute frequency for each column
    freq = [dict() for _ in range(word_len)]
    for word in words:
        for j, char in enumerate(word):
            freq[j][char] = freq[j].get(char, 0) + 1
    
    # dp[i] represents number of ways to form target[:i]
    dp = [0] * (target_len + 1)
    dp[0] = 1
    
    # Process each column
    for j in range(word_len):
        # Update in reverse to ensure we use previous state only
        for i in range(target_len, 0, -1):
            # If current target character exists in this column, update dp
            char = target[i-1]
            if char in freq[j]:
                dp[i] = (dp[i] + dp[i-1] * freq[j][char]) % mod
    
    return dp[target_len]

# Example usage:
words = ["acca", "bbbb", "caca"]
target = "aba"
print(numWays(words, target))  # Output: 6
← Back to All Questions