python - Substrings which contain only 'a', 'b' or 'c'
Question: I was coding for [this
problem.](https://www.hackerearth.com/problem/algorithm/substring/)

> Maggu has just joined play school. His teacher taught him A,a,B,b,C,c. He is
> much fascinated with these letters and now he is looking only for those
> strings which contains these letters only. But as i said he is a little guy
> he cant calculate the number of such sub-strings alone. Find the number of
> such strings.
    
    
    def substrings(string):
        for size in range(1, len(string)+1):
            for index in range(len(string)-size+1):
                yield string[index:index+size]
    
    l = []
    
    for x in range(int(raw_input())):
        l.append(raw_input().lower())
    
    not_ = 'defghijklmnopqrstuvwxyz'
    
    for string in l:
        count = 0
        for substr in substrings(string):
            if all(letter not in substr for letter in not_):
                count = count + 1
        print(count)
    

I realized that we can reduce the problem to lower case. I've wrote the code
but it is not efficient for large strings. And by large I mean exceptionally
large strings. I have realized that it is the `substrings` function that is
taking up a lot of time. How may I reduce the time consumption of the
`substrings` function? Can I replace it with some other code?

Thanks.


Answer: The reason why this is exponential is because you iterate over the same string
for different window lengths (up to len(string)). This is a job for regular
expressions, which will simply make one pass over your string to find any
sequences that contain the letters a, b, c, A, B, and C in succession at least
once.

After you have found these sequences, you can calculate their arithmetic
progression to count how many substrings each of those contain. To understand
why we have to use arithmetic progression, consider we have found the sequence
'abc' somewhere in the big string. The actual substrings of this sequence are
'a', 'ab', 'abc', 'b', 'bc', and 'c'. Basically, for a string of length n, we
can construct n substrings starting from the first letter, n-1 substrings
starting from the second letter, ..., and 1 substring starting from the last
letter.

    
    
    import re
    
    def count_substrings(string):
        found = re.findall('[a-cA-C]+', string)
        count = 0
        for f in found:
            length = len(f)
            count += length * (length + 1) / 2
        return count
    

For the example shown in the link

    
    
    >>> strings = ['AXa', 'ABC', 'AXBC', 'AaBbCc', 'XxYyZz']
    >>> for s in strings:
    ...    print(count_substrings(s))
    
    2
    6
    4
    21
    0
    

* * *

If you want to implement what `re.findall()` does yourself, you can try the
following.

    
    
    found = []
    substring = ''
    for s in string:
        if s in 'abcABC':
            substring += s
        else:
            # if we had a sequence going, it just ended, so add it to our found list
            if substring:
                found.append(substring)
                substring = ''
    # make sure to append the last sequence we had been working on
    if substring:
        found.append(substring)
    

