Moksh_grover's blog

By Moksh_grover, history, 4 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 .

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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 in O(n^3 log^2(n)).

Spoiler
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it