Find a string | HackerRANK

 We gone find how many time substring occur in each substring, we usinde kind of sliding window approach here where we slide the window range of fixed sub_string size

string = 'QAABDNSA'

k = 3

n = len(string)

sub_string = 'AA'

ocr = 0

for  i in range(n-k+1):

     left = i

     right = i  + k

     sub_array = string[left:right]

     print(sub_array)

     if sub_string in sub_array:

         print("yes")

         ocr += 1

     else:

         print("no")

     

print(ocr)

''' In this challenge, the user enters a string and a substring. You have to print the number of times that the substring occurs in the given string. String traversal will take place from left to right, not from right to left.'''

Solution:

def count_substring(string, sub_string):

    n = len(string)

    k = len(sub_string)

    ocr = 0

    for i in range(n-k+1):

        # left = i

        # right = i + k

        # sub_str = string[left:right]

        # if sub_str in string:

        #     ocr  = ocr  + 1

        if string[i:i+k] in sub_string:

            ocr += 1

       

 

    return ocr

Time: O((n-k+1)*k)

Space: O(1)