How should I practice Count Secured Strings?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Count Secured Strings associated with Amazon?

FastPrep tags this as a Amazon online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Count Secured Strings

Learn this problem

● Hard

AmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

In an Amazon security analysis task, two passwords have been generated, but they may be differ in length. One password is generated by a customer, and the other by an internal system. The customer wants to determine how many secured variations of the passwords exist module 10^9 + 7.

An secured variation of the passwords is defined as a subsequence of customer's password which is lexicographically greater than system generated password.

Formally:

Person A has a password s (the customer's password)

Person B has a password t (the system-generated password)

The task is to count how many susequences of password s are lexicographically greater than password t. Since the answer can be large, return the result module (%) 10^9 + 7. More specifically, if result represents the required number of subsequences, then return the remainder when result is divided by 10^9 + 7.

Note

A subsequence is determined 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 susequence of "abc", but "ca" is not.

A sequence x is considered lexicographically greater than a 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).

💜 Thanks a jillion, spike! 💜

Function

amazonCountSecuredStrings(s: String, t: String) → int

Examples

Example 1

s = "aba"t = "ab"return = 3

From all posibble subsequences, 3 are lexicographically smaller, 1 is equal, and 3 are greater than t, hence the answer is 3 :)

Example 2

s = "bab"t = "ab"return = 5

Lets examine all possible susequences that can be derived from s = "bab" and compare them lexicographically with t = "ab": The rest of the explanation is not complete, so I did not add them here :)

Constraints

1 <= |s| <= 10^5
1 <= |t| <= 100
s and t consists of lowercase English letters.