Unique Substrings of Length k

Moderate

0/80

1 upvote

Problem statement

You are given a string password and an integer k. Your task is to find the number of distinct (unique) substrings of length exactly k that exist within the password.

A substring is a contiguous sequence of characters. For example, in the string "ababa" with k=3, the substrings of length 3 are "aba", "bab", and "aba". The set of unique substrings is {"aba", "bab"}, so the total count is 2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer k, the desired length of the substrings.

The second line contains the string password.

Output Format:

Print a single integer representing the count of unique substrings of length k.

Note:

The problem constraints make it important to use an efficient data structure for storing and counting the unique substrings. A hash set is an excellent choice for this, as it automatically handles duplicates.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

The substrings of length 3 are:
  "aba" (starting at index 0)
  "bab" (starting at index 1)
  "aba" (starting at index 2)
The unique substrings are {"aba", "bab"}. The count is 2.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

The substrings of length 2 are "ab", "bc", "cd", "de".
All of them are unique. The count is 4.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

1 <= k <= length of password
1 <= length of password <= 10^5
The password consists of lowercase English letters.

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Unique Substrings of Length k

Console