### Moksh_grover's blog

By Moksh_grover, history, 6 weeks ago,

## Problem Statement

Given three strings p, q, r. Count the possible number of ways to create string r using string p and string q such that,the order of the selected characters in all the strings is preserved and atleast one characters from both the string is selected.

## Constraint

• Strings will have max length 100
• They will consist of lowercase english alphabets.
• Return the answer modulo 10^9+7

## Sample Test Case

• p :"ab"
• q :"ba"
• r :"aba"

Output : 2

### Explanation

Two ways to form aba :
1. from p 'a' ,from q 'ba'
2. from p 'ab' ,from q 'a'

This problem was asked in recent coding rounds .Can somebody help me with the solution?

• +2

 » 6 weeks ago, # | ← Rev. 7 →   -11 I think this should work. mod = 10**9 + 7 p, q, r = input().strip().split() cache = {} # i tracks the current position in string p # j tracks the current position in string q # r tracks the current position in string r def dp(i, j, k, pickedP, pickedQ): if k == len(r): # Atleast 1 character from each string constraint. if pickedP and pickedQ: return 1 return 0 if (i, j, k, pickedP, pickedQ) in cache: return cache[(i, j, k, pickedP, pickedQ)] res = 0 if i < len(p): if p[i] == r[k]: res += dp(i + 1, j, k + 1, True, pickedQ) else: res += dp(i + 1, j, k, pickedP, pickedQ) if j < len(q): if q[j] == r[k]: res += dp(i, j + 1, k + 1, pickedP, True) else: res += dp(i, j + 1, k, pickedP, pickedQ) res %= mod cache[(i, j, k, pickedP, pickedQ)] = res return res print(dp(0, 0, 0, False, False)) 
 » 6 weeks ago, # |   0 an approach similar to the classic 'Interleaving Strings' problem should work
 » 6 weeks ago, # |   +3 why so many uber question ? Have they started to gain new markets by the way following all the Uber interview questions made one thing clear to me.i would n't be able to qualify it .
•  » » 6 weeks ago, # ^ |   0 These questions are from the on-campus uber paper. They're selecting freshers.
 » 6 weeks ago, # | ← Rev. 2 →   0 I haven't tested it yet, but this will do. This solution is in O(n^4). You can modify it a bit using 2d fenwick tree or other data structures to make the solution runs in O(n^3 log^2(n)). Spoiler#pragma gcc optimize ("O3") #pragma gcc optimize ("unroll-loops") #include #define fi first #define se second #define pb(a) push_back(a) #define mp(a, b) make_pair(a, b) #define el '\n' using namespace std; using ll = long long; using pii = pair; const int N = 110; const ll MOD = 1e9 + 7; int n, m, k; string a, b, c; ll dp[N][N][N]; // [pos_a][pos_b][pos_c] = count int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> a >> b >> c; n = a.size(); m = b.size(); k = c.size(); // 1-indexing a = "*" + a; b = "*" + b; c = "*" + c; dp[0][0][0] = 1; for (int i=0;i<=n;i++){ for (int j=0;j<=m;j++){ for (int len=0;len
 » 6 weeks ago, # |   0 it is similar to this problem at hackerrank. https://www.hackerrank.com/contests/codeagon/challenges/number-of-ways-1