Description
Solutions
Valid Passwords
🔥 FULLTIME

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)

    Example 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.

    Example 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:
      • 2 ≤ n ≤ 105
      • 2 ≤ k ≤ n
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: