Counting Substrings: In a given text, find the number of substrings that start with an A and end with a B

Question

For example, there are four such substrings in CABAAXBYA.

The original brute force algorithm that I used was, Using an outer for loop, whenever I encounter an A, I go inside another for loop to check if there's a B present or not. If a B is found, I increment the count. Finally, the value stored in the count variable yields the required result.

I came across a point while reading about String matching algorithms, when you traverse right to left rather than left to right, your algorithm is more efficient but here the substring isn't given as a parameter to the function that you would be using to compute the required value.

My question is if I traverse the string from right to left instead of left to right, will it make my algorithm more efficient in any case?

Answer 1

Here is one way in which iterating backwards through the string could result in O(n) computation instead of your original O(n^2) work:

A = "CABAAXBYA"

count = 0 # Number of B's seen
total = 0
for a in reversed(A):
    if a=='B':
        count += 1
    elif a=='A':
        total += count

print total

This works by keeping track in count of the number of B's to the right of the current point.

(Of course, you could also get the same result with forwards iteration by counting the number of A's to the left instead:

count = 0 # Number of A's seen
total = 0
for a in A:
    if a=='A':
        count += 1
    elif a=='B':
        total += count
print total

)