Diverse Substrings (Codeforces 1748B)
Tags: Implement, strings

A non-empty digit string is diverse if the number of occurrences of each character in it doesn't exceed the number of distinct characters in it.For example:   string "7" is diverse because 7 appears in it $$$1$$$ time and the number of distinct characters in it is $$$1$$$;  string "77" is not diverse because 7 appears in it $$$2$$$ times and the number of distinct characters in it is $$$1$$$;  string "1010" is diverse because both 0 and 1 appear in it $$$2$$$ times and the number of distinct characters in it is $$$2$$$;  string "6668" is not diverse because 6 appears in it $$$3$$$ times and the number of distinct characters in it is $$$2$$$. You are given a string $$$s$$$ of length $$$n$$$, consisting of only digits $$$0$$$ to $$$9$$$. Find how many of its $$$\frac{n(n+1)}{2}$$$ substrings are diverse.A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.Note that if the same diverse string appears in $$$s$$$ multiple times, each occurrence should be counted independently. For example, there are two diverse substrings in "77" both equal to "7", so the answer for the string "77" is $$$2$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the string $$$s$$$.The second line of each test case contains a string $$$s$$$ of length $$$n$$$. It is guaranteed that all characters of $$$s$$$ are digits from $$$0$$$ to $$$9$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print one integer — the number of diverse substrings of the given string $$$s$$$. 

Note: In the first test case, the diverse substring is "7".In the second test case, the only diverse substring is "7", which appears twice, so the answer is $$$2$$$.In the third test case, the diverse substrings are "0" ($$$2$$$ times), "01", "010", "1" ($$$2$$$ times), "10" ($$$2$$$ times), "101" and "1010".In the fourth test case, the diverse substrings are "0" ($$$3$$$ times), "01", "011", "0110", "1" ($$$2$$$ times), "10", "100", "110" and "1100".In the fifth test case, the diverse substrings are "3", "39", "399", "6", "9" ($$$4$$$ times), "96" and "996".In the sixth test case, all $$$15$$$ non-empty substrings of "23456" are diverse.

Sample Inputs:
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798

Sample Outputs:
1
2
10
12
10
15
106

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    n = readInt()
    s = [int(v) for v in readStr()]
    ans = 0
    for i in range(n):
        cnt = [0] * 10
        occ = dist = 0
        for j in range(i, min(n, i + 101)):
            if cnt[s[j]] == 0:
                dist += 1
            cnt[s[j]] += 1
            occ = max(occ, cnt[s[j]])
            if occ <= dist:
                ans += 1
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = 0
    for k in range(len(s)):
        sus = [0 for i in range(10)]
        temp = 0
        maxi = -1
        for i in range(105):
            if k + i >= len(s):
                continue
            now = ord(s[k + i]) - ord('0')
            if sus[now] == 0:
                temp += 1
            sus[now] += 1
            maxi = max(maxi, sus[now])
            ans += maxi <= temp
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    s = list(input().rstrip())
    s = [i - 48 for i in s]
    ans0 = 0
    for i in range(n):
        cnt = [0] * 10
        (ma, u) = (0, 0)
        for j in range(i, min(i + 100, n)):
            sj = s[j]
            cnt[sj] += 1
            if cnt[sj] == 1:
                u += 1
            ma = max(ma, cnt[sj])
            if ma <= u:
                ans0 += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))