Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

meiniak's blog

By meiniak, history, 8 months ago, In English

Given an array of strings, each of the same length and a target string construct the target string using characters from the strings in the given array such that the indices of the characters in the order in which they are used form a strictly increasing sequence. Here the index of a character is the position at which it appears in the string. Note that it is acceptable to use multiple characters from the same string. Determine the number of ways to construct the target string. One construction is different from another if either the sequences of indices they use are different, or the sequences are the same but there exists a character at some index such that it is chosen from a different string in these constructions. Since the answer can be very large, return the value modulo (109 + 7). Consider an example with n = 3 strings, each of length 3. Let the array of strings be words = ["adc", "aec", "erg"], and the target string target = "ac". There are 4 ways to reach the target.

  1. Select the 1st character of "adc" and the 3rd character of "adc".
  2. Select the 1st character of "adc" and the 3rd character of "aec".
  3. Select the 1st character of "aec" and the 3rd character of "adc".
  4. Select the 1st character of "aec" and the 3rd character of "aec".
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints on string lengths, sum of string lengths and number of strings? If number of strings (k) is very small and strings (n, m) are at most ~10^3 in length then you can do O(nmk2^k) dp by considering all permutations of the array (O(k2^k), like doing tsp) and counting all occurrences (n*m like doing edit distance)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the number of strings in can be atmost 10^3 having each string length of 20 i guess. I didn't understand your solution can you please explain more clearly or can suggest some similar problems ? Thanx

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With those constraints, what you can do is iterate over all strictly increasing sequences of indexes (they are at most 2^20), and for every sequence count in how many ways can you select the string for each index so that you form the target string.

      In your example, the sequences are [[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]. You can ignore the sequences with length different from 2 (as that is the length of the target string). That leaves us with [[0,1],[0,2],[1,2]]. For each of these sequences we can count in how many ways we can select strings to form the target:

      • For the sequence [0,1], there are 2 ways to select a string to get the letter 'a' at the 0th position and there are 0 ways to select a string to get the letter 'c' at the 1st position. This sequence gives us 0*2=0 ways to form the target.

      • The sequence [1,2] also gives us 0 ways (there are 0 ways to select a string from the 1st position and 2 for the 2nd position, giving a total of 0).

      • For the sequence [0,2], there are 2 ways to select a string to get the letter 'a' from the 0th position and there are 2 ways to select a string to get the letter 'c' from the 2nd position. Thus, this sequence gives us 2*2=4 ways to form the target.

      If you sum these up, there are 0+0+4=4 ways to form the target string.

      Sample code implementing this idea: https://pastebin.com/GhQLfgnK

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

A much better solution than anything exponential is a DP where your state is your index in the target string, and your index in every other string. Your transition is either skip this index in every given string and go to the next index, or for each string take it if it matched the next char in the target.

Naively this is O(n*m*k) if your target is n long and you have k strings of length m, but you can easily optimize it to just O(n*m) by noting that you don’t care which strings are which, just how many of each char are at each index in any of your k strings.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can the target have many identical letters?