Perfect Substring
Updated
Problem statement
You are given a string s containing only digits and a positive integer k.
A nonempty contiguous substring is perfect if every digit that appears in it occurs exactly k times. Digits absent from the substring do not matter.
Return the number of perfect substring occurrences. Count different index intervals separately, even when their text is identical, and include overlapping occurrences.
Function
perfectSubstring(s: String, k: int) → intExamples
Example 1
s = "1102021222"k = 2return = 6Using 0-based inclusive endpoints, the six intervals are [0,1], [0,5], [1,6], [2,5], [7,8] and [8,9]. Their texts are respectively 11, 110202, 102021, 0202, 22 and 22. Each present digit occurs twice. The final two intervals overlap and are counted separately.
Example 2
s = "1020122"k = 2return = 2The perfect intervals are [0,5], whose text is 102012, and [5,6], whose text is 22. Each present digit occurs twice, giving two occurrences.
Example 3
s = "1221221121"k = 3return = 3The perfect intervals are [2,7], [3,8] and [4,9], with texts 212211, 122112 and 221121. Each contains three 1s and three 2s, so all three qualify.
Constraints
1 <= s.length <= 1000001 <= k <= 100000- The string s contains only digits 0 through 9.
Similar questions at other companies
- Maximum Valid Substring FrequencyMicrosoft · OAMicrosoft interview questions
- Longest Distinct StringSuperhuman · OASuperhuman interview questions
- Longest Substring Without Repeating CharactersAkuna Capital · OAAkuna Capital interview questions
- Perfect SubstringsVisa · OAVisa interview questions
- Vowel SubstringSnowflake · OASnowflake interview questions
- Count Distinct Fixed-Length SubstringsAdobe · OAAdobe interview questions
- Video ID Generation (Generic)TikTok · OATikTok interview questions
- Unaligned DedupeRubrik · OARubrik interview questions
- Get Max OccurrencesIBM · OAIBM interview questions
- Find P-Matching ScoreAmazon · OA