Count Distinct Ways to Form Target from Two Strings - Solution & Explanation

Problem Overview: You need to count how many distinct ways a target string can be formed by choosing characters from two source strings while preserving character order. The challenge comes from handling overlapping subproblems efficiently because many index combinations lead to the same remaining state.

Approach 1: Recursive Brute Force (Exponential Time, O(2^(n+m)) time, O(n+m) space)

The direct approach uses recursion to try every valid choice from both strings. At each step, you compare the current target character against characters from the two source strings and recursively continue when a match is found. This works for very small inputs because it explores every subsequence combination explicitly. The main drawback is repeated computation of the same index states, which causes exponential growth.

Approach 2: Top-Down Dynamic Programming with Memoization (O(n*m*k) time, O(n*m*k) space)

This is the standard interview solution. Use a memoized DFS where the state is defined by indices in the first string, second string, and target string. For each state, iterate forward in both source strings to locate matching characters and accumulate the number of valid constructions. Memoization eliminates duplicate work by caching results for repeated states. This approach is easier to reason about than iterative DP and maps naturally to the recursive definition of the problem. It combines dynamic programming with recursion to reduce the search space dramatically.

Approach 3: Bottom-Up DP with Prefix Optimization (O(n*m*k) time, O(n*m) space)

An iterative DP solution avoids recursion depth issues and gives tighter memory control. Build a DP table where each cell stores the number of ways to form a prefix of the target using prefixes of the two strings. Transition values come from previous states when matching characters are found. Prefix accumulation or rolling arrays can reduce memory usage while keeping transitions efficient. This version is useful when you need production-grade stability or strict stack constraints.

Approach 4: Character Index Preprocessing + DP (Optimized Lookup)

You can preprocess character positions for both source strings using arrays or hash maps. During DP transitions, binary search or indexed traversal quickly finds the next valid matching positions instead of scanning linearly every time. This optimization improves constant factors significantly on larger inputs with repeated characters. It pairs well with hash table based indexing and memoized search.

Recommended for interviews: Interviewers typically expect the memoized dynamic programming solution because it demonstrates state modeling, pruning, and complexity optimization. Showing the brute force recursion first proves you understand the search space, while transitioning to DP shows the ability to identify overlapping subproblems and optimize them systematically.