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?
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 .
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 inO(n^3 log^2(n)).it is similar to this problem at hackerrank. https://www.hackerrank.com/contests/codeagon/challenges/number-of-ways-1