FastPrep
Problem · String

Perfect Substrings

Learn this problem
● MediumVisa logoVisaFULLTIMEOA

Problem statement

Given a digit string s and a positive integer k, count its non-empty substrings in which every digit that appears occurs exactly k times.

Return the total as a 64-bit integer. Two substrings with the same contents are counted separately when they occupy different index ranges.

Function

countPerfectSubstrings(s: String, k: int) → long

Examples

Example 1

s = "11020211"k = 2return = 6

The six qualifying ranges have contents 11, 110202, 102021, 0202, 020211, and the final 11. Repeated contents at different positions count separately.

Example 2

s = "2222"k = 2return = 3

Each length-two range contains the only present digit exactly twice, so all three length-two ranges qualify.

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s contains only digits from 0 through 9.
  • 1 <= k <= s.length

More Visa problems

drafts saved locally
public long countPerfectSubstrings(String s, int k) {
    // Write your code here.
}
s"11020211"
k2
expected6
checking account