Given 2 Strings, count positions where substrings of Length K Match.
Input : test_str1 = ‘neveropen’, test_str2 = ‘peeksformeeks’, K = 4
Output : 4
Explanation : 4 positions match K length Substrings.
Input : test_str1 = ‘neveropen’, test_str2 = ‘peeksformeeks’, K = 5
Output : 3
Explanation : 3 positions match K length Substrings.
Method #1 : Using list comprehension + min() + slicing
In this, we iterate through strings till length of minimum string, and the comparison is done by slicing using string slicing. Iteration is done through loop inside list comprehension.
Python3
# Python3 code to demonstrate working of # Number of positions where Substrings Match of Length K# Using list comprehension + min() + slicing# initializing stringstest_str1 = 'neveropen'test_str2 = 'peeksformeeks'# printing original stringsprint("The original string 1 is : " + str(test_str1))print("The original string 2 is : " + str(test_str2))# initializing K K = 3# checking for substrings, # using len() to get total countres = len([test_str1[idx : idx + K] for idx in range(min(len(test_str1), len(test_str2)) - K - 1) if test_str1[idx : idx + K] == test_str2[idx : idx + K]])# printing result print("Number of positions of matching K length Substrings : " + str(res)) |
The original string 1 is :neveropen The original string 2 is : peeksformeeks Number of positions of matching K length Substrings : 5
Method #2 : Using map() + list comprehension
In this, we extract all K length substrings of one string and then using in operator and map, check for each substring if present in other String, this ignores the positional factor of problem.
Python3
# Python3 code to demonstrate working of # Number of positions where Substrings Match of Length K# Using map() + list comprehension# initializing stringstest_str1 = 'neveropen'test_str2 = 'peeksformeeks'# printing original stringsprint("The original string 1 is : " + str(test_str1))print("The original string 2 is : " + str(test_str2))# initializing K K = 3# Extracting Substringssubs_str = [test_str1[idx : idx + K] for idx in range(len(test_str1) - K - 1)]# checking in other string# using count() to get numberres = list(map(lambda ele: ele in test_str2, subs_str)).count(True)# printing result print("Number of positions of matching K length Substrings : " + str(res)) |
The original string 1 is :neveropen The original string 2 is : peeksformeeks Number of positions of matching K length Substrings : 5
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3: Using set intersection and zip function
Step by step Algorithm:
- Initialize the strings and the length of the matching substrings (K).
- Create two sets using the zip() function to get tuples of (character in test_str1, character in test_str2) for both strings, where the tuples are created for the indices up to K-1.
- Get the set difference between the two sets obtained in step 2 to get all the tuples of matching substrings.
- Count the number of elements in the resulting set.
- Subtract 1 from the count obtained in step 4 to exclude the overlap at the start of the strings.
- Return the count as the final result.
Python3
test_str1 = 'neveropen'test_str2 = 'peeksformeeks'# printing original stringsprint("The original string 1 is : " + str(test_str1))print("The original string 2 is : " + str(test_str2))# initializing KK = 3# using set intersection and zip function to countres = len(set(zip(test_str1, test_str2)) - set(zip(test_str1[:K-1], test_str2[:K-1])))res = res-1;# printing resultprint("Number of positions of matching K length Substrings : " + str(res)) |
The original string 1 is :neveropen The original string 2 is : peeksformeeks Number of positions of matching K length Substrings : 9
Time complexity: O(n), where n is the length of the shortest string.
Space complexity: O(n), where n is the length of the shortest string.
