Nice Pairs solution codechef

Nice Pairs solution codechef

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

Nice Pair is a pair of indices – (i,j)(i,j) such that 1i<jN1≤i<j≤N and ji=|SjSi|j−i=|Sj−Si|.

Input Format Nice Pairs solution codechef

  • First line will contain TT, number of testcases. Then the testcases follow.
  • The first line of each testcase contains a single integer, NN, the length of the string
  • The second line of each testcase contains a string SS of length NN. The string contains only numeric characters [09][0−9]

Output Format Nice Pairs solution codechef

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

Constraints Nice Pairs solution codechef

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • String SS contains only numeric characters
  • The sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1  Nice Pairs solution codechef

3
3
123
5
13492
8
94241234

Sample Output 1  Nice Pairs solution codechef

3
2
9

Explanation

Test Case 11: There are 33 nice pairs in the given string – (1,2),(1,3),(2,3)(1,2),(1,3),(2,3)

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

Leave a Comment