Quick Overview

Count all digit substrings in which each distinct digit appears exactly a specified number of times. This challenge tests combinatorial bounds, compact frequency state, efficient window reasoning over a fixed alphabet, and use of a sufficiently wide result type.

Count Perfect Digit-Frequency Substrings

Company: Visa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Count Perfect Digit-Frequency Substrings ### Problem Implement `countPerfectSubstrings(s, k)`. The string `s` contains only decimal digits. A nonempty substring is perfect when every distinct digit that occurs in that substring occurs exactly `k` times. Count substring occurrences by their start and end positions, even when two occurrences have the same text. Return the total number of perfect substrings. ### Function Contract - Python: `def countPerfectSubstrings(s: str, k: int) -> int` - JavaScript: `function countPerfectSubstrings(s, k)` returns an exact integer `Number`. - Java: `long countPerfectSubstrings(String s, int k)` - C++: `long long countPerfectSubstrings(const string& s, int k)` ### Examples ```text s = "11020211" k = 2 output = 6 ``` The six occurrences are the two copies of `"11"`, `"0202"`, and the three length-six substrings `"110202"`, `"102021"`, and `"020211"`. ```text s = "123" k = 1 output = 6 ``` Every nonempty substring contains each of its digits once. ```text s = "000" k = 2 output = 2 ``` The two length-two occurrences are counted separately. ### Constraints - `1 <= s.length <= 90,000`. - `1 <= k <= 90,000`. - `s[i]` is one of `0` through `9`. - Let `B` be the byte length of `[s,k]` serialized as compact UTF-8 JSON with no whitespace outside strings. Because `s` contains only digits and `k` uses canonical decimal notation, no string escapes are needed. Inputs satisfy `B <= 96,000`. - The answer is at most `s.length * (s.length + 1) / 2`, which is at most `4,050,045,000`. It is exact in JavaScript integer arithmetic and requires a 64-bit return type in Java and C++. - Let `R` be the compact JSON byte length of the returned integer. `R <= 10`, so serialized input plus result is at most `96,010` bytes. - Do not modify or rebuild `s` into a quadratic collection of substrings. - Target `O(10 * s.length)` time and `O(1)` auxiliary space beyond fixed-size digit counters. ```hint Use the alphabet size If a valid substring contains `d` distinct digits, its length must be exactly `d * k`, and `d` can only range from one through ten. ``` ### Discussion Requirements 1. Explain why checking every start and end pair is too slow. 2. Show how the ten possible distinct-digit counts limit the window lengths that matter. 3. Describe how a sliding window maintains digit frequencies and recognizes a perfect window. 4. Explain why the result type must handle values above `2^31 - 1`.

Quick Answer: Count all digit substrings in which each distinct digit appears exactly a specified number of times. This challenge tests combinatorial bounds, compact frequency state, efficient window reasoning over a fixed alphabet, and use of a sufficiently wide result type.

Implement `countPerfectSubstrings(s, k)`. `s` is a nonempty string made only of decimal digit characters. A nonempty substring of `s` is **perfect** when every distinct digit that occurs in that substring occurs **exactly** `k` times. Digits that do not occur in the substring place no requirement on it. Count substring **occurrences**, identified by their `(start, end)` index pair. Two occurrences with identical text at different positions count separately. Return the total number of perfect substring occurrences. ### Function contract - Python: `def countPerfectSubstrings(s, k)` - JavaScript: `function countPerfectSubstrings(s, k)`, returning an exact integer `Number` - Java: `public long countPerfectSubstrings(String s, int k)` - C++: `long long countPerfectSubstrings(const std::string& s, int k)` ### Output semantics Return a single nonnegative integer: the count of perfect substring occurrences. The answer is a single number, so it is uniquely determined by `(s, k)` — there is no ordering, tie-breaking, or formatting choice to make. Return `0` when no perfect substring exists, which includes every input where `k > s.length`. ### Examples **Example 1** ```text Input: s = "11020211", k = 2 Output: 6 ``` The six occurrences are the two copies of `"11"` (indices 0-1 and 6-7), `"0202"` (indices 2-5), and the three length-six substrings `"110202"` (0-5), `"102021"` (1-6) and `"020211"` (2-7). Each length-six window holds exactly three distinct digits, each appearing exactly twice. **Example 2** ```text Input: s = "123", k = 1 Output: 6 ``` Each of the six nonempty substrings — `"1"`, `"2"`, `"3"`, `"12"`, `"23"`, `"123"` — contains every digit it uses exactly once. **Example 3** ```text Input: s = "000", k = 2 Output: 2 ``` `"00"` occurs at indices 0-1 and at indices 1-2, and the two occurrences are counted separately. The full string is not perfect because `'0'` occurs three times, not two.

Constraints

  • 1 <= s.length <= 90,000
  • 1 <= k <= 90,000
  • s[i] is one of the characters '0' through '9'; s contains no other characters and is never empty
  • k > s.length is a valid input and always yields 0
  • Let B be the byte length of [s, k] serialized as compact UTF-8 JSON with no whitespace outside strings. Because s contains only digits and k uses canonical decimal notation, no string escapes are needed. Inputs satisfy B <= 96,000
  • The answer is at most s.length * (s.length + 1) / 2, which is at most 4,050,045,000. It is exact in JavaScript integer arithmetic (far below 2^53) and requires a 64-bit return type in Java (long) and C++ (long long)
  • Let R be the compact JSON byte length of the returned integer. R <= 10, so serialized input plus result is at most 96,010 bytes
  • Do not modify or rebuild s into a quadratic collection of substrings
  • Target O(10 * s.length) time and O(1) auxiliary space beyond fixed-size digit counters

Examples

Input: ('11020211', 2)

Expected Output: 6

Input: ('123', 1)

Expected Output: 6

Hints

  1. If a perfect substring uses d distinct digits and each occurs exactly k times, its length is forced to be exactly d * k. Since s holds only decimal digits, d can only be 1 through 10 — so only ten window lengths are ever worth examining.
  2. Once a window length is fixed, one left-to-right pass suffices: as the window advances by one position, exactly one character enters and one leaves, so ten digit counters can be maintained in O(1) per step.
  3. Deciding whether the current window is perfect does not require rescanning it. Ask what small running tallies over the ten counters would let you answer 'is every digit present in this window present exactly k times, and are there exactly d of them?' in constant time.

Loading coding console...