Frontend School

Count Substrings with K Distinct Characters

DSA
easy

Count Substrings with K Distinct Characters

Easy
String
Sliding Window
Hash Map

Overview

In Livspace's inventory management system, product codes sometimes have embedded segments that need to be unique to ensure proper identification. For auditing and quality control, we need to quickly identify how many segments of a specific length within a larger product code string contain only distinct characters. This helps in validating the integrity and uniqueness of generated codes.

What you need to do / Task

Implement a function countSubstringsWithKDistinct that takes a string s and an integer k. The function should return the total count of all substrings of s that have a length of exactly k and contain exactly k distinct characters.

Input & output

  • Input:
    • s: A string representing the main product code. s consists of lowercase English letters.
    • k: An integer representing the required length of the substrings to check.
  • Output: An integer, the total count of such substrings that satisfy both conditions (length k and k distinct characters).

Clarifications

  • A substring is a contiguous sequence of characters within a string.
  • 'Distinct characters' means that all characters within the substring are unique (no repetitions).
  • If k is 1, any single character substring is considered to have 1 distinct character.

Examples

1

Example 1

Input:

s = "abcabc", k = 3

Output:

4

Note:

Substrings of length 3:

  • "abc" (distinct: a,b,c) -> Valid
  • "bca" (distinct: b,c,a) -> Valid
  • "cab" (distinct: c,a,b) -> Valid
  • "abc" (distinct: a,b,c) -> Valid Total valid substrings: 4.
2

Example 2

Input:

s = "aaabbb", k = 3

Output:

0

Note:

Substrings of length 3:

  • "aaa" (distinct: a) -> Invalid (only 1 distinct char)
  • "aab" (distinct: a,b) -> Invalid (only 2 distinct chars)
  • "abb" (distinct: a,b) -> Invalid (only 2 distinct chars)
  • "bbb" (distinct: b) -> Invalid (only 1 distinct char) Total valid substrings: 0.
3

Example 3

Input:

s = "abacaba", k = 3

Output:

2

Note:

Substrings of length 3:

  • "aba" (distinct: a,b) -> Invalid
  • "bac" (distinct: b,a,c) -> Valid
  • "aca" (distinct: a,c) -> Invalid
  • "cab" (distinct: c,a,b) -> Valid
  • "aba" (distinct: a,b) -> Invalid Total valid substrings: 2.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= k <= s.length
  • s consists of lowercase English letters.

What interviewers evaluate

  • Correctness: The solution must accurately count all valid substrings, handling various inputs and edge cases.
  • Efficiency: The solution should achieve optimal time complexity, ideally linear (O(N)), using appropriate data structures.
  • Clarity and Structure: The code should be well-organized, readable, and demonstrate a clear understanding of the chosen algorithm.
  • Problem-Solving: Ability to identify and apply the sliding window technique effectively.

Loading editor...