Given a string consisting of symbols ., A and B, count the number of symbols which are either A, or are . (dots) and next and previous non-dot symbols in the string are A. Also, calculate this count with respect to symbols B.
Consider the characters one-by-one, maintain last non-dot symbol last_symbol and the number of dots num_dots since the last character. Whenever the current symbol is non-dot and is the same as last, add the number of dots since the last symbol.
Consider one of the symbols to calculate the answer for, for example, A. Which symbols contribute to the answer? First, of course, all occurrences of A in the string give a +1. However, we are also interested in dots that are preceded and followed by A-s (when considering non-dot symbols). Let’s consider a block of consecutive dots; clearly, they either all contribute +1 to answer if they are surrounded by A-s, or give nothing. When we iterate over the characters from left to right, we can maintain how many symbols are there in the current block of consecutive dots, and which symbol preceded it. We can actually find answers for A and B in a single pass. Whenever we meet a dot, we increment the counter of consecutive dots (num_dots). Whenever a non-dot symbol is met, we check whether the symbol that preceded block of dots is the same as current. If so, we add num_dots to the answer. We also reset the counter in this case.
The solution works in O(|s|) time (we only consider each character once) and requires O(1) additional memory (apart from the O(|s|) memory to store the input string) because we only use the constant amount of variables.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.