Given a String and substring, count all the substitutes from string that can be used to complete the substring.
Input : test_str = “Gfg is good . Gfg is good . Gfg is better . Gfg is good .”, substr = “Gfg is”
Output : {‘good’: 3, ‘better’: 1}
Explanation : good occurs 3 times as suffix after substring in string hence 3. and so on.
Input : test_str = “Gfg is good . Gfg is good . Gfg is good . Gfg is good .”, substr = “Gfg is”
Output : {‘good’: 4}
Explanation : good occurs 4 times as suffix after substring in string hence 4. and so on.
Method #1 : Using regex() + defaultdict() + loop
This is one of the ways in which this task can be performed. In this, we construct regex for getting all the matching elements for substring. Then check all possible occurrences in String, frequency count using defaultdict().
Python3
# Python3 code to demonstrate working of# Substring substitutes frequency# Using regex() + defaultdict() + loopfrom collections import defaultdictimport re# initializing stringtest_str = "Gfg is good . Gfg is best . Gfg is better . Gfg is good ."# printing original stringprint("The original string is : " + str(test_str))# initializing substringsubstr = "Gfg is"# initializing regextemp = re.findall(substr + " (\w+)", test_str, flags = re.IGNORECASE)# adding values to form frequenciesres = defaultdict(int)for idx in temp: res[idx] += 1# printing resultprint("Frequency of replacements : " + str(dict(res))) |
The original string is : Gfg is good . Gfg is best . Gfg is better . Gfg is good .
Frequency of replacements : {'good': 2, 'best': 1, 'better': 1}
Method #2 : Using Counter() + regex()
This is yet another way in which this task can be performed. In this, we compute elements frequency using Counter().
Python3
# Python3 code to demonstrate working of# Substring substitutes frequency# Using Counter() + regex()import refrom collections import Counter# initializing stringtest_str = "Gfg is good . Gfg is best . Gfg is better . Gfg is good ."# printing original stringprint("The original string is : " + str(test_str))# initializing substringsubstr = "Gfg is"# initializing regextemp = re.findall(substr + " (\w+)", test_str, flags = re.IGNORECASE)# adding values to form frequenciesres = dict(Counter(temp))# printing resultprint("Frequency of replacements : " + str(res)) |
The original string is : Gfg is good . Gfg is best . Gfg is better . Gfg is good .
Frequency of replacements : {'good': 2, 'best': 1, 'better': 1}
Method #3 : Using split(),find(),count(),strip() methods
Python3
# Python3 code to demonstrate working of# Substring substitutes frequency# initializing stringtest_str = "Gfg is good . Gfg is good . Gfg is better . Gfg is good ."# printing original stringprint("The original string is : " + str(test_str))# initializing substringsubstr = "Gfg is"x=test_str.split(".")y=[]for i in x: if(i.find(substr)!=-1): i=i.strip().split(" ") y.append(i[-1])y1=list(set(y))d=dict()for i in y1: d[i]=y.count(i)# printing resultprint("Frequency of replacements : " + str(d)) |
The original string is : Gfg is good . Gfg is good . Gfg is better . Gfg is good .
Frequency of replacements : {'good': 3, 'better': 1}
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(n)
Space Complexity: O(n)
Method #4 : Using operator.countOf() methods
Python3
# Python3 code to demonstrate working of# Substring substitutes frequencyimport operator as op# initializing stringtest_str = "Gfg is good . Gfg is good . Gfg is better . Gfg is good ."# printing original stringprint("The original string is : " + str(test_str))# initializing substringsubstr = "Gfg is"x=test_str.split(".")y=[]for i in x: if(i.find(substr)!=-1): i=i.strip().split(" ") y.append(i[-1])y1=list(set(y))d=dict()for i in y1: d[i]=op.countOf(y,i)# printing resultprint("Frequency of replacements : " + str(d)) |
The original string is : Gfg is good . Gfg is good . Gfg is better . Gfg is good .
Frequency of replacements : {'better': 1, 'good': 3}
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using list comprehension and dictionary comprehension
Step by step approach:
- Split the original string into a list of sentences using the split() method and the period character as the separator.
- Filter out the non-matching sentences using a list comprehension that checks if the substring is present in each sentence using the in keyword.
- Strip the whitespace from each sentence using the strip() method.
- Extract the last word of each matching sentence using a list comprehension that splits each sentence into words using the split() method and gets the last element using the -1 index.
- Create a set of the unique last words using the set() function.
- Count the frequency of each last word using a dictionary comprehension that uses the count() method of the list of last words to count the occurrences of each unique word.
- Print the result.
Python3
# initializing stringtest_str = "Gfg is good . Gfg is good . Gfg is better . Gfg is good ."# initializing substringsubstr = "Gfg is"# split the string into sentences and filter out non-matching sentencessentences = [s.strip() for s in test_str.split('.') if substr in s]# extract the last word of each matching sentencelast_words = [s.split()[-1] for s in sentences]# count the frequency of each last wordfreq = {w: last_words.count(w) for w in set(last_words)}# print the resultprint("Frequency of replacements : " + str(freq)) |
Frequency of replacements : {'good': 3, 'better': 1}
The time complexity of this approach is O(n), where n is the number of characters in the input string.
The space complexity of this approach is O(m), where m is the number of unique last words in the input string.
