Round 1
Questions: A secured variation of the passwords is defined as a subsequence of customers password which is lexicographically greater than system generated password.
Formally:
- person A has a password s (the customers password)
- person B has a password t (the system generated password)
The task is to count how many subsequences of password s are lexicographically greater than password t. Since the answer can be large, return the result modulo 10^9 + 7.
Note:
- A subsequence is defined as a sequence derived from the original password by deleting zero or more characters without changing the order of the remaining characters. For example "ac" is a subsequence of "abc", but "ca" is not.
- x is considered lexicographically greater than sequence y if x[i] > y[i] at the first position where x and y differ, or |x| > |y| and y is a prefix of x (where |x| denotes the length of password x)
Example 1:
s = "aba" t = "ab"
All possible subsequences of s = aba:
- a - smaller than t="ab"
- ab - equal
- aa - smaller
- aba - greater
- b - greater
- ba - greater
- a - smaller
Of all possible subsequences of s: 3 are smaller, 1 equal and 3 are greater than t so the answer is 3.
Example 2:
s = "bab" t = "ab"
All possible subsequences of s = bab:
- b - greater
- ba - greater
- bb - greater
- bab - greater
- a - smaller
- ab - equal
- b - greater
Of all possible subsequences of s: 1 is smaller, 1 is equal and 5 are greater than t, so the answer is 5.
Constraints:
- 1<=|s|<10000
- 1<=|t|<100
- s and t are lowercase english letters
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.