Frontend School

Count K-Beautiful Substrings

DSA
medium

Count K-Beautiful Substrings

Medium
String
Sliding Window
Hash Map

Overview

At Snap, we often process user-generated content, including text. Analyzing properties of text, such as character diversity within specific segments, can be crucial for content moderation, recommendation engines, or even stylistic analysis for creative tools. This problem challenges you to identify and count specific types of substrings based on their character diversity.

What you need to do / Task

You are tasked with implementing a function countKBeautifulSubstrings that takes a string s and an integer k. Your function should return the total number of substrings of s that contain exactly k distinct characters.

Input & output

  • Input:
    • s: A string consisting of lowercase English letters.
    • k: An integer representing the required number of distinct characters.
  • Output:
    • An integer, the total count of K-beautiful substrings.

Clarifications

  • A substring is a contiguous sequence of characters within a string.
  • An empty string s will result in 0 beautiful substrings.
  • If k is greater than the total distinct characters available in s, the count will be 0.
  • Substrings must be non-empty.

Examples

1

Example 1

Input:

s = "aba", k = 2

Output:

3

Note:

The K-beautiful substrings are "ab", "ba", and "aba".

2

Example 2

Input:

s = "aabc", k = 2

Output:

3

Note:

The K-beautiful substrings are "ab", "aab", and "bc".

3

Example 3

Input:

s = "aaaaa", k = 1

Output:

15

Note:

All substrings of "aaaaa" contain exactly 1 distinct character ('a'). The number of substrings is n*(n+1)/2 = 5*6/2 = 15.

4

Example 4

Input:

s = "abcde", k = 4

Output:

2

Note:

The K-beautiful substrings are "abcd" and "bcde".

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= k <= 26 (since s consists only of lowercase English letters)
  • s consists only of lowercase English letters ('a'-'z').

Out of scope

  • Handling non-alphabetic characters or uppercase letters.
  • Optimizations for extremely large alphabets (e.g., Unicode characters).

What interviewers evaluate

  • Ability to design an efficient algorithm for substring analysis, specifically using a sliding window technique.
  • Correctness in managing and updating distinct character counts within the sliding window.
  • Clarity, organization, and readability of the implemented code.
  • Proper handling of various edge cases and adherence to problem constraints.
  • Optimal time and space complexity for the given problem scale.

Loading editor...