FastPrep
Problem · Dynamic Programming

Valid Passwords

● MediumMathWorksFULLTIMEOA

Hackerbank allows all citizens of the city of Hackerland to maintain their finances.

In order to ensure security, given two integers n and k, a password is valid if:

  • The length of the password is n.
  • The password consists of lowercase English characters only.
  • The password does not contain k consecutive equal characters.

    • Given the integers n and k, find the number of distinct valid passwords that can be generated. Since the answer can be large, compute it modulo (109 + 7).

    Function Description

    Complete the function countValidPasswords in the editor.

    countValidPasswords has the following parameters:

    • int n: the length of the password
    • int k: the number of matching consecutive characters should be less than this number

    Returns

    int: the number of valid passwords, modulo (109 + 7)

    Examples
    01 · Example 1
    n = 3
k = 3
return = 17550
    The number of passwords possible of length 3 are 26*26*26. Subtract the cases where all the characters are the same (26 such cases). The number of valid passwords is 26*26*26 - 26 = 17550 and 17550 % (109 + 7) = 17550.
    02 · Example 2
    n = 3
k = 2
return = 16250
    The number of passwords possible of length 3 is 26*26*26. Subtract the cases where all the characters are the same (26 such cases) 26*26*26 - 26 = 17550. Subtract cases like "aab" and "baa" where two consecutive characters are the same, 26*25 * 26*25. The number of valid passwords is 26*26*26 - 26*25 - 26*25 - 26 = 16250 and 16250 % (109 + 7) = 16250.
    Constraints
    • 2 ≤ n ≤ 105
    • 2 ≤ k ≤ n
    More MathWorks problems
    drafts saved locally
    public int countValidPasswords(int n, int k) {
  // write your code here
}
    n3
    k3
    expected17550
    sign in to submit