Frontend School

Minimum Window with Specific Character Frequencies

DSA
hard

Minimum Window with Specific Character Frequencies

Hard
Sliding Window
Hash Map
String

Overview

In many real-world applications, such as log analysis, genomic sequencing, or network packet inspection, identifying the smallest contiguous segment that contains a specific pattern of characters with certain minimum frequencies is crucial. This problem challenges you to implement an efficient algorithm to find such a segment, ensuring optimal resource utilization and processing speed.

What you need to do / Task

Given a string s and a list of character frequency requirements requiredCounts, your task is to find the shortest contiguous substring of s that satisfies all the specified frequency requirements. Each character in requiredCounts must appear in the substring at least its corresponding required number of times.

Input & output

  • Input:
    • s: A string consisting of uppercase English letters.
    • requiredCounts: An array of [character: string, count: number] pairs. Each character is an uppercase English letter, and count is its minimum required frequency.
  • Output:
    • Return the shortest contiguous substring of s that meets all requiredCounts. If multiple substrings have the same minimum length, any one of them is acceptable. If no such substring exists, return an empty string "".

Clarifications

  • s will only contain uppercase English letters ('A'-'Z').
  • Characters in requiredCounts are guaranteed to be unique.
  • The problem is case-sensitive (only uppercase letters are considered).
  • If requiredCounts is empty, an empty string "" should be returned (as no requirements need to be met).
  • If s is empty, an empty string "" should be returned (as no substring can be formed).

Examples

1

Example 1

Input:

s = "ADOBECODEBANC", requiredCounts = [["A", 1], ["B", 1], ["C", 1]]

Output:

"BANC"

Note:

The substring "ADOBEC" contains A, B, C but has length 6. The substring "BANC" also contains A, B, C (from 'A' at index 9, 'B' at index 10, 'C' at index 11) and has length 4, which is the minimum.

2

Example 2

Input:

s = "ABBCABBA", requiredCounts = [["A", 2], ["B", 3]]

Output:

"BBCA"

Note:

The substring "ABBCAB" has 2 'A's and 3 'B's (length 6). The substring "BBCA" also has 2 'A's (from 'A' at index 6) and 3 'B's (from 'B' at index 3, 4, 7) and has length 4, which is the minimum.

3

Example 3

Input:

s = "AA", requiredCounts = [["A", 3]]

Output:

""

Note:

The string "AA" only has 2 'A's. It cannot satisfy the requirement of at least 3 'A's. Therefore, no valid substring exists.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • s consists of uppercase English letters ('A'-'Z').
  • 0 <= requiredCounts.length <= 26
  • 1 <= count <= s.length for each [char, count] in requiredCounts.
  • Characters in requiredCounts are unique.

Out of scope

  • Error handling for invalid input types (e.g., non-string s, negative counts).
  • Optimizations for extremely sparse requiredCounts (e.g., specific data structures for very few distinct characters).

What interviewers evaluate

  • Correct application of the sliding window technique to efficiently explore substrings.
  • Accurate management of character frequencies within the window to satisfy dynamic requirements.
  • Proper handling of edge cases, such as when no valid substring exists or when requiredCounts is empty.
  • Optimal time and space complexity, demonstrating an understanding of efficient algorithm design.

Loading editor...