FastPrepFastPrep
Problem Brief

Count Secured Strings

FULLTIMEOA
See Amazon online assessment and 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! 💜

    1Example 1

    Input
    s = "aba", t = "ab"
    Output
    3
    Explanation
    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 :)

    2Example 2

    Input
    s = "bab", t = "ab"
    Output
    5
    Explanation
    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

    Limits and guarantees your solution can rely on.

    • 1 <= |s| <= 10^5
    • 1 <= |t| <= 100
    • s and t consists of lowercase English letters.
    public int amazonCountSecuredStrings(String s, String t) {
  // write your code here
}
    Input

    s

    "aba"

    t

    "ab"

    Output

    3

    Sign in to submit your solution.