Given a string S of length N containing only numeric characters, find the number of Nice Pairs.

A Nice Pair is a pair of indices - (i, j) such that 1 ≤ i < j ≤ N and j - i = |S_{j} - S_{i}|.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- The first line of each testcase contains a single integer, N, the length of the string
- The second line of each testcase contains a string S of length N. The string contains only numeric characters [0-9]

------ Output Format ------ 

For each testcase, output a single integer - the number of nice pairs in the given string.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
- String $S$ contains only numeric characters
- The sum of $N$ over all test cases does not exceed $2\cdot10^{5}$

----- Sample Input 1 ------ 
3
3
123
5
13492
8
94241234

----- Sample Output 1 ------ 
3
2
9

----- explanation 1 ------ 
Test Case $1$: There are $3$ nice pairs in the given string - $(1,2) , (1,3) , (2,3)$

Test Case $2$: There are $2$ nice pairs in the given string - $(2,3) , (3,5)$

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input()))
	c = 0
	for j in range(n):
		for k in range(j + 1, n):
			if j + 1 == n or k - j > 9:
				break
			elif k - j == abs(L[k] - L[j]):
				c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(input().strip())
	l = list(map(int, l))
	ans = 0
	for i in range(n):
		for k in range(1, 10):
			j = i + k
			if j >= n:
				continue
			if abs(l[i] - l[j]) == k:
				ans += 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	np = 0
	for i in range(n):
		for j in range(i + 1, min(n, i + 10)):
			if j - i == abs(int(s[j]) - int(s[i])):
				np += 1
	print(np)
	t -= 1


for _ in range(int(input())):
	ans = 0
	n = int(input())
	s = input()
	for i in range(n - 1):
		for j in range(i + 1, i + 10):
			if j < n:
				if abs(int(s[i]) - int(s[j])) == j - i:
					ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ct = 0
	for i in range(n - 1):
		for j in range(i + 1, min(i + 12, n)):
			if abs(int(s[i]) - int(s[j])) == j - i:
				ct += 1
	print(ct)


for i in range(int(input())):
	k1 = int(input())
	str1 = input()
	c1 = 0
	for k in range(k1):
		for j in range(k + 1, min(k + 11, k1)):
			if abs(k - j) == abs(int(str1[k]) - int(str1[j])):
				c1 += 1
	print(c1)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	k = 0
	for i in range(n - 1):
		for j in range(i + 1, i + 10):
			if j > n - 1:
				break
			elif j - i == abs(int(s[j]) - int(s[i])):
				k = k + 1
	print(k)


for _ in range(int(input())):
	n = int(input())
	s = input()
	nice = 0
	for i in range(len(s) - 1):
		for j in range(i + 1, i + 10):
			if j > n - 1:
				break
			elif j - i == abs(int(s[i]) - int(s[j])):
				nice += 1
	print(nice)


for x in range(int(input())):
	n = int(input())
	a = input()
	s = []
	count = 0
	for i in range(n):
		for j in range(i + 1, min(n, i + 10)):
			if j - i == abs(int(a[i]) - int(a[j])):
				count += 1
	print(count)


for i in range(int(input())):
	leng = int(input())
	stri = input()
	nuu = 0
	for j in range(leng):
		for m in range(j + 1, min(j + 10, leng)):
			if m - j == abs(int(stri[j]) - int(stri[m])):
				nuu += 1
	print(nuu)


for i in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for j in range(n):
		for k in range(j + 1, min(j + 10, n)):
			if k - j == abs(int(s[j]) - int(s[k])):
				ans += 1
	print(ans)


def solve(arr):
	ans = 0
	for i in range(len(arr)):
		for j in range(1, min(10, len(arr) - i)):
			if abs(int(arr[i]) - int(arr[i + j])) == j:
				ans += 1
	return ans
for _ in range(int(input())):
	a = input()
	print(solve(input()))


for t in range(int(input())):
	n = int(input())
	s = input()
	res = 0
	if n < 10:
		for i in range(n - 1):
			for j in range(i + 1, n):
				if j - i == abs(int(s[i]) - int(s[j])):
					res += 1
		print(res)
		continue
	for i in range(n - 9):
		for j in range(1, 10):
			if j == abs(int(s[i]) - int(s[i + j])):
				res += 1
	for i in range(n - 9, n - 1):
		for j in range(i + 1, n):
			if j - i == abs(int(s[i]) - int(s[j])):
				res += 1
	print(res)


for i in range(int(input())):
	cnt = int(input())
	string = input()
	count = 0
	for i in range(cnt - 1):
		j = i + 1
		while j <= min(i + 9, cnt - 1):
			if abs(int(string[i]) - int(string[j])) == j - i:
				count += 1
			j += 1
	print(count)


for i in range(int(input())):
	a = int(input())
	b = str(input())
	c = 0
	for i in range(1, a + 1):
		for k in range(i + 1, min(9 + i, a) + 1):
			if k - i == abs(int(b[k - 1]) - int(b[i - 1])):
				c += 1
	print(c)


t = int(input())
for m in range(t):
	x = int(input())
	l = input()
	count = 0
	for i in range(x):
		for j in range(i + 1, min(x, i + 11)):
			p = abs(int(l[i]) - int(l[j]))
			if j - i == p:
				count = count + 1
	print(count)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(input())
	count = 0
	for i in range(len(a)):
		k = i + 1
		while k <= min(i + 9, n - 1):
			if abs(int(a[k]) - int(a[i])) == k - i:
				count += 1
			k += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in range(len(s)):
		a = int(s[i])
		for j in range(i + 1, min(n, i + 10)):
			b = int(s[j])
			if int(abs(j - i)) == abs(a - b):
				count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		j = i + 1
		while j <= min(i + 9, n - 1):
			if abs(int(s[i]) - int(s[j])) == j - i:
				count += 1
			j += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	c = 0
	for i in range(n):
		j = i + 1
		while j <= min(i + 9, n - 1):
			if j - i == abs(int(s[j]) - int(s[i])):
				c += 1
			j += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		num1 = int(s[i])
		for j in range(i + 1, min(n, i + 10)):
			num2 = int(s[j])
			if abs(num1 - num2) == j - i:
				count += 1
	print(count)


import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
from collections import defaultdict

def solve():
	n = int(input())
	s = list(map(int, list(input())))
	s1 = defaultdict(int)
	s2 = defaultdict(int)
	for i in range(n):
		s1[s[i] + i] += 1
		s2[s[i] - i] += 1
	(value1, value2) = (0, 0)
	for v in s1.values():
		value1 += v * (v - 1) // 2
	for v in s2.values():
		value2 += v * (v - 1) // 2
	print(value1 + value2)
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, min(n, i + 10)):
			if j - i == abs(int(s[j]) - int(s[i])):
				count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	srng = input()
	cnt = 0
	for i in range(n):
		ind = i
		for j in range(i + 1, min(i + 9, n - 1) + 1):
			if j - i == abs(int(srng[j]) - int(srng[i])):
				cnt += 1
	print(cnt)


from collections import defaultdict
T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, list(input())))
	p = 0
	d = defaultdict(int)
	d1 = defaultdict(int)
	for i in range(n):
		d[s[i] + i] += 1
		d1[s[i] - i] += 1
	(a, b) = (0, 0)
	for v in d.values():
		a += v * (v - 1) // 2
	for v in d1.values():
		b += v * (v - 1) // 2
	print(a + b)


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		count = 0
		for i in range(n):
			for j in range(i + 1, min(n - 1, i + 9) + 1):
				if j - i == abs(int(s[j]) - int(s[i])):
					count += 1
		print(count)
except Exception:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		p = int(s[i])
		for j in range(i + 1, min(n - 1, i + 9) + 1):
			p1 = int(s[j])
			if abs(p1 - p) == j + 1 - (i + 1):
				c = c + 1
	print(c)


t = int(input())

def solve(s):
	s = list(map(int, list(s)))
	(c, n) = (0, len(s))
	for i in range(n):
		for j in range(i + 1, min(i + 10, n)):
			if abs(s[i] - s[j]) == j - i:
				c += 1
	return c
for _ in range(t):
	n = int(input())
	x = input()
	print(solve(x))


T = int(input())
for a in range(T):
	N = int(input())
	s = input()[:N]
	c = 0
	for i in range(len(s)):
		for j in range(i + 1, min(N, i + 9 + 1)):
			if j - i > 9:
				continue
			if j - i == abs(int(s[j]) - int(s[i])):
				c = c + 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, list(input())))
	c = 0
	for j in range(n):
		for k in range(j + 1, min(j + 10, n)):
			if k - j == abs(s[j] - s[k]):
				c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, list(input())))
	count = 0
	for i in range(n):
		for j in range(i + 1, min(n, i + 10)):
			if j - i == abs(s[i] - s[j]):
				count += 1
	print(count)


for i in range(int(input())):
	N = int(input())
	a = input()
	c = 0
	for i in range(0, len(a)):
		for j in range(i + 1, len(a)):
			if j - i > 9:
				break
			elif j - i == abs(int(a[j]) - int(a[i])):
				c = c + 1
	print(c)


for i in range(int(input())):
	n = int(input())
	arr = str(input())
	count = 0
	for i in range(1, n + 1):
		for j in range(i + 1, min(9 + i, n) + 1):
			if j - i == abs(int(arr[j - 1]) - int(arr[i - 1])):
				count += 1
	print(count)


t = int(input())
for i in range(t):
	a = int(input())
	b = input()
	c = 0
	for i in range(1, a + 1):
		for k in range(i + 1, min(10 + i, a + 1)):
			if k - i == abs(int(b[k - 1]) - int(b[i - 1])):
				c += 1
	print(c)


for t in range(int(input())):
	n = int(input())
	l = input()
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if j - i > 9:
				break
			elif abs(int(l[j]) - int(l[i])) == j - i:
				c += 1
	print(c)


T = int(input())
for i in range(T):
	n = int(input())
	ip = str(input())
	cnt = 0
	for i in range(n):
		for j in range(i + 1, min(i + 10, n)):
			if j - i == abs(int(ip[j]) - int(ip[i])):
				cnt = cnt + 1
	print(cnt)


t = int(input())
while t:
	n = int(input())
	s = input()
	string = []
	for i in s:
		string.append(int(i))
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if j - i > 9:
				break
			diff = abs(string[i] - string[j])
			if diff == j - i:
				count += 1
	print(count)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(1, len(s) + 1):
		for j in range(i + 1, min(9 + i, n) + 1):
			if j - i == abs(int(s[j - 1]) - int(s[i - 1])) and int(s[j - 1]) - int(s[i - 1]) != 0:
				c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input()]
	cnt = 0
	for j in range(n - 1):
		for k in range(j + 1, min(j + 10, n)):
			if abs(arr[k] - arr[j]) == k - j:
				cnt += 1
	print(cnt)


def fun(ls):
	neg_mod = []
	pos_mod = []
	for (i, val) in enumerate(ls, start=1):
		neg_mod.append(val + i)
		pos_mod.append(val - i)
	neg_value_with_index = {}
	pos_value_with_index = {}
	for (index, val) in enumerate(zip(neg_mod, pos_mod), start=1):
		neg_mod_val = val[0]
		pos_mod_val = val[1]
		if neg_value_with_index.get(neg_mod_val) != None:
			neg_value_with_index[neg_mod_val].append(index)
		else:
			neg_value_with_index[neg_mod_val] = [index]
		if pos_value_with_index.get(pos_mod_val) != None:
			pos_value_with_index[pos_mod_val].append(index)
		else:
			pos_value_with_index[pos_mod_val] = [index]
	ans = 0
	for (index, i) in enumerate(neg_mod, start=1):
		all_indexes = neg_value_with_index.get(i)
		for j in all_indexes:
			if index <= j:
				break
			elif ls[index - 1] < ls[j - 1]:
				ans += 1
	for (index, i) in enumerate(pos_mod, start=1):
		all_indexes = pos_value_with_index.get(i)
		for j in all_indexes:
			if index <= j:
				break
			elif ls[index - 1] >= ls[j - 1]:
				ans += 1
	print(ans)
T = int(input())
for i in range(T):
	n = input()
	st = list(input())
	ls = list(map(int, st))
	fun(ls)


t = int(input())
for i in range(t):
	a = int(input())
	b = input()
	c = 0
	for i in range(a):
		for j in range(i + 1, min(a, i + 11)):
			if j - i == abs(int(b[j]) - int(b[i])):
				c = c + 1
	print(c)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		a = 0
		l = str(input())
		for i in range(1, n + 1):
			for j in range(i + 1, min(9 + i, n) + 1):
				if j - i == abs(int(l[j - 1]) - int(l[i - 1])):
					a += 1
		print(a)
except:
	pass


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		for j in range(i + 1, i + 10):
			if j < n:
				if j - i == abs(int(s[j]) - int(s[i])):
					c = c + 1
	print(c)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
yy = lambda : print('YES')
nn = lambda : print('NO')
from math import log10, log2, ceil, factorial as fac, gcd, inf, sqrt, log
from bisect import bisect_right as br, bisect_left as bl, insort
from collections import Counter
mod = 10 ** 9 + 7

def Nprime(n):
	if n == 2 or n == 3:
		return 0
	if n == 1:
		return 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 1
		i += 1
	return 0

def g(n):
	i = 2
	while n % i == 0:
		i += 1
	return i

def char(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans
for _ in range(t()):
	n = t()
	a = list(map(int, input()))
	ans = 0
	for i in range(n):
		for j in range(i + 1, min(i + 10, n)):
			if abs(a[i] - a[j]) == j - i:
				ans += 1
	print(ans)


import sys
import os.path
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
m1 = float('inf')
if os.path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp().split())

def power(n):
	return 1 << n

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)
for _ in range(ninp()):
	(n, s) = (ninp(), sinp())
	c = 0
	for i in range(0, n):
		m1 = min(9 + i, n - 1)
		for j in range(i + 1, m1 + 1, 1):
			val = j - i
			if val == abs(int(s[i]) - int(s[j])):
				c = c + 1
	prnt(c)


t = int(input())
for k in range(t):
	n = int(input())
	s = str(input())
	count = 0
	for i in range(1, n + 1):
		for j in range(i + 1, min(n, i + 9) + 1):
			if int(j) > int(i) and int(j) - int(i) == abs(int(s[j - 1]) - int(s[i - 1])):
				count += 1
	print(count)


try:
	for i in range(int(input())):
		a = int(input())
		b = [int(x) for x in input()]
		c = 0
		for i in range(a):
			for k in range(i + 1, min(10 + i, a)):
				if k - i == abs(b[k] - b[i]):
					c += 1
		print(c)
except:
	pass


def NPAIRS(inputline1: int, inputline2: str) -> int:
	size = inputline1
	numbers = list(inputline2)
	numbers = [int(i) for i in numbers]
	numbers = numbers + ['dead']
	maincount = 0
	for i in range(size):
		temp = 0
		while temp < 9:
			temp += 1
			if numbers[i + temp] == 'dead':
				temp = 0
				break
			if temp == abs(numbers[i + temp] - numbers[i]):
				maincount += 1
	return maincount
TestCases = int(input())
for i in range(TestCases):
	inputline1 = int(input())
	inputline2 = str(input())
	output = NPAIRS(inputline1, inputline2)
	print(output)


for _ in range(int(input())):
	n = int(input())
	s = input()
	counter = 0
	for i in range(n):
		for j in range(i + 1, min(n, i + 10)):
			if abs(int(s[j]) - int(s[i])) == j - i:
				counter += 1
	print(counter)


t = eval(input())
for i in range(t):
	n = eval(input())
	s = input()
	c = 0
	for i in range(1, n):
		for k in range(i + 1, min(9 + i, n) + 1):
			if k - i == abs(int(s[k - 1]) - int(s[i - 1])):
				c = c + 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	count = 0
	for i in range(n):
		j = i + 1
		while j < n and j <= i + 9:
			diff = j - i
			diff2 = abs(int(s[j]) - int(s[i]))
			if diff == diff2:
				count += 1
			j += 1
	print(count)


l = int(input())
for _ in range(l):
	m = int(input())
	a = str(input())
	temp = 0
	for i in range(1, m + 1):
		for j in range(i + 1, min(9 + i, m) + 1):
			if j - i == abs(int(a[j - 1]) - int(a[i - 1])):
				temp += 1
	print(temp)


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		for j in range(i + 1, min(n - 1, i + 9) + 1):
			if j - i == abs(int(s[i]) - int(s[j])):
				c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if j - i > 9:
				break
			if j - i == abs(int(s[j]) - int(s[i])):
				ans += 1
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	a = input()
	cnt = 0
	for i in range(n):
		for j in range(i + 1, min(i + 10, n)):
			v1 = abs(int(a[j]) - int(a[i]))
			if abs(j - i) == v1:
				cnt += 1
	print(cnt)
	t -= 1


t = int(input())
for _ in range(t):
	num = int(input())
	s = str(input())
	p = 0
	for i in range(len(s)):
		for j in range(i + 1, min(len(s), i + 10)):
			if j - i == abs(int(s[j]) - int(s[i])):
				p += 1
	print(p)