3981. Count Distinct Ways to Form Target from Two Strings

You are given three strings word1, word2, and target.

Your task is to count the number of ways to form target by choosing characters from word1 and word2 under the following conditions:

• For each character of target, choose one matching character from either word1 or word2.
• The chosen indices from word1 must be strictly increasing.
• The chosen indices from word2 must be strictly increasing.
• At least one character must be chosen from both word1 and word2.

Two ways are considered different if, for at least one position in target, the chosen character comes from a different string or a different index.

Return the number of ways. Since the answer may be very large, return it modulo 10^9 + 7.

class Solution {
    static const long long mod = 1000000007;
    long long dp[101][101][101];

    long long dfs(int pos, int i, int j, string& target, vector<vector<int>>& p1, vector<vector<int>>& p2) {
        if(pos == target.size()) return i > 0 && j > 0;

        long long& res = dp[pos][i][j];
        if(res != -1) return res;

        res = 0;
        int c = target[pos] - 'a';

        auto it1 = lower_bound(p1[c].begin(), p1[c].end(), i);
        for(; it1 != p1[c].end(); it1++) {
            res += dfs(pos + 1, *it1 + 1, j, target, p1, p2);
            res %= mod;
        }

        auto it2 = lower_bound(p2[c].begin(), p2[c].end(), j);
        for(; it2 != p2[c].end(); it2++) {
            res += dfs(pos + 1, i, *it2 + 1, target, p1, p2);
            res %= mod;
        }

        return res;
    }

public:
    int interleaveCharacters(string word1, string word2, string target) {
        vector<vector<int>> p1(26), p2(26);

        for(int i = 0; i < word1.size(); i++) {
            p1[word1[i] - 'a'].push_back(i);
        }

        for(int i = 0; i < word2.size(); i++) {
            p2[word2[i] - 'a'].push_back(i);
        }

        memset(dp, -1, sizeof dp);
        return dfs(0, 0, 0, target, p1, p2);
    }
};