Find occurrence of a string in another string

Question

Details:

• There are two strings x and y.

• Count the number of occurrence of y in x as follows:

  • Length of y is 3.

  • Increment the "count" value when y == x[i] x[i+2] x[i+4]

Example:

x = "aabbcc"
y = "abc" 
output: 2

My Code:

def solution(x, y):
    i, count = 0, 0
    j = i + 2
    k = i + 4
    
    while i+4 < len(x):
        cur = x[i]
        while i < len(x) and i != j:
            i += 1
        while i < len(x) and i != k:
            i += 1
        count += 1
        
    return count
    
solution(x, y)
            

I am getting count = 1. It should give count = 2

Answer 1

There's a couple of logic errors in your code.

The problem happens here:

        while i < len(x) and i != j:
            i += 1
        res.append(x[i])

You keep increasing i until it is either len(x) or greater, or until it is the same as j. But since you set j to be 2 at the start (and never update it), it will simply end up setting i to len(x). And x[i] will thus fail, since x[len(x)] tries to index an element just outside x.

However, there's a few more remarks to make:

• you collect what you find in res, but really only want a number (e.g. 2) as a result
• you define count but don't use it
• you track the coordinates in the string in three separate variables (i, j, k) and have a lot of logic to increment the first, but really all you need is to step through the string one position at a time, and look at the offsets directly

Given all that and the problem description, you were probably going for something like this:

x = "aabbcc"
y = "abc"


def solution(x, y):
    i, count = 0, 0

    while i + 4 < len(x):
        if (x[i], x[i+2], x[i+4]) == (y[0], y[1], y[2]):
            count += 1
        i += 1

    return count


print(solution(x, y))

However, Python has some cleverness that would make it even simpler (or at least shorter):

def solution(x, y):
    count = 0

    for i in range(len(x)-4):
        if x[i:i+5:2] == y:  # slicing with a stride of two, instead of direct indexing
            count += 1

    return count

Or even:

def solution(x, y):
    return len([x for i in range(len(x)-4) if x[i:i+5:2] == y])

But that's favouring brevity over readability a bit too much, I feel.

Answer 2

A generator expression solution, taking advantage of True/False == 1/0 in a numeric context:

def solution(x, y):
    return sum(y == x[i:i+5:2] for i in range(len(x)-4))

Answer 3

Increment the "count" value when y == x[i] x[i+2] x[i+4]

This is the same as simply creating the string consisting of x[0], x[2], x[4]... (every even-numbered character) and the string consisting of x[1], x[3], x[5]... (every odd-numbered character); counting the occurrences of y in each; and adding those two results together.

Creating the strings is trivial, and a common duplicate. Counting occurrences of a substring is also well-trodden ground. Putting these tools together:

def spread_substrings(needle, haystack):
    even_haystack = haystack[::2]
    odd_haystack = haystack[1::2]
    return even_haystack.count(needle) + odd_haystack.count(needle)