FastPrepFastPrep
Problem Brief

Valid Passwords

FULLTIMEOA

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)

    1Example 1

    Input
    n = 3, k = 3
    Output
    17550
    Explanation
    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.

    2Example 2

    Input
    n = 3, k = 2
    Output
    16250
    Explanation
    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

    Limits and guarantees your solution can rely on.

    • 2 ≤ n ≤ 105
    • 2 ≤ k ≤ n
    public int countValidPasswords(int n, int k) {
  // write your code here
}
    Input

    n

    3

    k

    3

    Output

    17550

    Sign in to submit your solution.