FastPrep
Problem · Dynamic Programming

Count Secured Strings

● HardAmazonFULLTIMEOA
See Amazon hiring insights

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! 💜

    Examples
    01 · Example 1
    s = "aba"
t = "ab"
return = 3
    Example 1 illustration
    From all posibble subsequences, 3 are lexicographically smaller, 1 is equal, and 3 are greater than t, hence the answer is 3 :)
    02 · Example 2
    s = "bab"
t = "ab"
return = 5
    Example 2 illustration
    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.
    More Amazon problems
    drafts saved locally
    public int amazonCountSecuredStrings(String s, String t) {
  // write your code here
}
    s"aba"
    t"ab"
    expected3
    checking account