[Solution] Paranoid String Codeforces Solution

[Solution] Paranoid String Codeforces Solution

B. Paranoid String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call a binary string T$T$ of length m$m$ indexed from 1$1$ to m$m$ paranoid if we can obtain a string of length 1$1$ by performing the following two kinds of operations m−1$m-1$ times in any order :

• Select any substring of T$T$ that is equal to 01, and then replace it with 1.
• Select any substring of T$T$ that is equal to 10, and then replace it with 0.

  For example, if T=$T=$ 001, we can select the substring [T2T3]$[T_2{T}_3]$ and perform the first operation. So we obtain T=$T=$ 01.

You are given a binary string S$S$ of length n$n$ indexed from 1$1$ to n$n$. Find the number of pairs of

Solution Click Below:-  CLICK HERE

 integers (l,r)$(l,r)$ 1≤l≤r≤n$1\le l\le r\le n$ such that S[l…r]$S[l\dots r]$ (the substring of S$S$ from l$l$ to r$r$) is a paranoid string.

Input

The first line contains an integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — the size of S$S$.

Creep Codeforces Solution

Paranoid String Codeforces Solution

Directional Increase Codeforces Solution

Fake Plastic Trees Codeforces Solution

Keshi in Search of AmShZ Codeforces Solution

Decinc Dividing Codeforces Solution

The second line of each test case contains a binary string S$S$ of n$n$ characters S1S2…Sn$S_1{S}_2\dots S_n$. (Si=$S_i=$ 0 or Si=$S_i=$ 1 for each 1≤i≤n$1\le i\le n$)

It is guaranteed that the sum of n$n$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output the number of pairs of integers (l,r)$(l,r)$ 1≤l≤r≤n$1\le l\le r\le n$ such that S[l…r]$S[l\dots r]$ (the substring of S$S$ from l$l$ to r$r$) is a paranoid string.