Substrings In Substring :
Difficulty Level : Medium
Submissions : 254
Asked In :
Marks :15
: 6 | : 0
You are given a $$$1$$$-indexed string $$$S$$$ of length $$$n$$$ having only lowercase Latin letters. We call a substring that starts and ends with the same character as a good substring. Note that a single character is also considered as a good substring.
You need to answer $$$q$$$ queries of the following type:
- $$$l$$$ $$$r$$$ — Find the number of good substrings of the substring $$$S[l...r]$$$
More formally, for each query, you need to print the number of substrings of the string $$$S[l...r]$$$ which start and end with the same character.
The first line of each testcase contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains two space separated integers $$$n$$$ and $$$q$$$ — the length of the string $$$s$$$ and the number of queries respectively.
The second line of each testcase contains string $$$s$$$ containing $$$n$$$ lowercase Latin letters.
The next $$$q$$$ lines each contain two space separated integers $$$l$$$ and $$$r$$$ denoting the queries.
It is guaranteed that the individual sums of $$$n$$$ and $$$q$$$ over all testcases does not exceed $$$10^5$$$ respectively.
For each testcase, print the answer to each query in a single line.
24 2aabc1 23 46 4abcaab1 12 53 61 6
3 2 1 5 5 10
For sample test case 1,
- For the $$$1^{st}$$$ query, $$$l=1$$$, $$$r=2$$$. We have $$$3$$$ substrings that satisfy the above condition, $$$S[1,1]$$$, $$$S[1,2]$$$ and $$$S[2,2]$$$.
- For the $$$2^{nd}$$$ query, $$$l=3$$$, $$$r=4$$$. We have $$$2$$$ substrings that satisfy the above condition, $$$S[3,3]$$$, $$$S[4,4]$$$.
