How to find number or 'xx' pairs in a barcode recursively (python)

Question

I am using python. Im having trouble with this recursion problem, I am trying to find how many pairs of characters are the same in a string. For example, 'xx' would return 1 and 'xxx' would also return one because the pairs are not allowed to overlap. 'aabbb' would return 2.

I am completely stuck. I thought of breaking the word up into length 2 strings and recursing through the string like that, but then cases like 'aaa' would result in incorrect output.

Thanks.

Answer 1

You can use regex for that:

import re

s = 'yyourr ssstringg'
print len(re.findall(r'(\w)\1', s))

[OUTPUT]
4

This also takes care of your "overlaps-not-allowed" problem as you can see in the above example it prints 4 and not 5.

For a recursion approach, you can do it as:

st = 'yyourr ssstringg'

def get_double(s):
    if len(s) < 2:
        return 0
    else:
        for i,k in enumerate(s):
            if k==s[i+1]:
                return 1 + get_double(s[i+2:])

>>> print get_double(st)
4

And without a for loop:

st = 'yyourr sstringg'

def get_double(s):
    if len(s) < 2:
        return 0
    elif s[0]==s[1]:
        return 1 + get_double(s[2:])
    else:
        return 0 + get_double(s[1:])

>>> print get_double(st)
4

Answer 2

Not sure why you want to do this recursively. If you wish to avoid regex, you can still just scan the string from left to right. For example, using itertools.groupby

>>> from itertools import groupby
>>> s = 'aabbb'
>>> sum(sum(1 for i in g)//2 for k,g in groupby(s))
2
>>> s = 'yyourr ssstringg'
>>> sum(sum(1 for i in g)//2 for k,g in groupby(s))
4

sum(1 for i in g) is used to find the length of the group. If the groups are not very long you can use len(list(g)) instead

Answer 3

I would evaluate it by 2's.

for example "sskkkj" would be looked at as two sets of two char strings:

"ss", "kk", "kj" # from 0 index
"sk", "kk"  # offset by 1 

look at the two sets at the same time and add only one to the count if either has a pair.