given a string s comprising of the characters 0, 1, and ?. We should call a string unsteady in the event that it comprises of the characters 0 and 1 and any two contiguous characters are unique (I. e. it has the structure 010101... or then again 101010...). How about we call a string delightful in the event that it
Computer science. Correct answer will be upvoted else downvoted.
You are given a string s comprising of the characters 0, 1, and ?.
We should call a string unsteady in the event that it comprises of the characters 0 and 1 and any two contiguous characters are unique (I. e. it has the structure 010101... or then again 101010...).
How about we call a string delightful in the event that it comprises of the characters 0, 1, and ?, and you can supplant the characters ? to 0 or 1 (for each character, the decision is free), so the string becomes shaky.
For instance, the strings 0??10, 0, and ??? are wonderful, and the strings 00 and ?1??1 are not.
Ascertain the number of delightful adjacent substrings of the string s.
Input
The main line contains a solitary integer t (1≤t≤104) — number of experiments.
The solitary line of each experiment contains the string s (1≤|s|≤2⋅105) comprising of characters 0, 1, and ?.
It is ensured that the amount of the string lengths over all experiments doesn't surpass 2⋅105.
Output
For each experiment, output a solitary integer — the number of wonderful substrings of the string s.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
