Count occurrences of a sub-string with one variable character
Given two strings a and b, and an integer k which is the index in b at which the character can be changed to any other character, the task is to check if b is a sub-string in a and print out how many times b occurs in a in total after replacing the b[k] with every possible lowercase character of English alphabet. Examples:
Input: a = “feeds”, b = “ee”, k = 1
Output: 1 Replace b[1] with ‘k’ and “ed” is a sub-string in “feeds” “ee” is also a sub-string in “feeds” Hence the total count is 2
Input: a = “dogdog”, b = “dop”, k = 2
Output: 2 Replace b[2] with ‘g’, “dog” is a sub-string in “dogdog” which appears twice.
Approach: Make a list of all possible versions of the string b by iterating through all the lowercase letters and replacing the kth i.e. b[k] character in b with the current character. Then count the number of occurrences of the new string b in the original string a and store it in a variable count. After all the lowercase characters are used, print the count.
Below is the implementation of the above approach:
Python3
# Python3 implementation of the approachimport string# Function to return the count of occurrencesdef countOccurrence(a, b, k): # Generate all possible substrings to # be searched x = [] for i in range(26): x.append(b[0:k] + string.ascii_lowercase[i] + b[k + 1:]) # Now search every substring 'a' and # increment count count = 0 for var in x: if var in a: count += a.count(var) return count# Driver codea, b = "feeds", "ee"k = 1print(countOccurrence(a, b, k)) |
Output:
2