Given a string and a substring, write a Python program to find the nth occurrence of the string. Let’s discuss a few methods to solve the given task.
Get Nth occurrence of a substring in a String using regex
Here, we find the index of the ‘ab’ character in the 4th position using the regex re.finditer()
Python3
import re# Initialising valuesini_str = "abababababab"substr = "ab"occurrence = 4# Finding nth occurrence of substringinilist = [m.start() for m in re.finditer(r"ab", ini_str)]if len(inilist)>= 4: # Printing result print ("Nth occurrence of substring at", inilist[occurrence-1])else: print ("No {} occurrence of substring lies in given string".format(occurrence)) |
Output:
Nth occurrence of substring at 6
Get Nth occurrence of a substring in a String using find() method
Here, we find the index of the ‘ab’ character in the 4th position using the str.find().
Python3
# Initialising valuesini_str = "abababababab"sub_str = "ab"occurrence = 4# Finding nth occurrence of substringval = -1for i in range(0, occurrence): val = ini_str.find(sub_str, val + 1) # Printing nth occurrenceprint ("Nth occurrence is at", val) |
Output:
Nth occurrence is at 6
Get Nth occurrence of a substring in a String using startswith()
Here, we find the index of the ‘ab’ character in the 4th position using the str.startwith().
Python3
# Initialising valuesini_str = "abababababab"substr = "ab"occurrence = 4# Finding nth occurrence of substringinilist = [i for i in range(0, len(ini_str)) if ini_str[i:].startswith(substr)]if len(inilist)>= 4: # Printing result print ("Nth occurrence of substring at", inilist[occurrence-1])else: print ("No {} occurrence of substring lies in given string".format(occurrence)) |
Output:
Nth occurrence of substring at 6
Get Nth occurrence of a substring in a String using split()
Here, we find the index of the ‘ab’ character in the 4th position using the split().
Python3
def solve(s, str, n): sep = s.split(str, n) if len(sep) <= n: return -1 return len(s) - len(sep[-1]) - len(str)print('length: ', len('dellGeeks asusfor neveropendell'))print("position", solve('dellGeeks asusfor neveropendell', 'dell', 2)) |
Output:
length: 35 position 31
The time complexity of the given code is O(n), where n is the length of the input string s.
The space complexity of the code is O(n), where n is the length of the input string s.
Using the count() method:
Approach:
Use the count() method to find the total number of occurrences of the substring in the given string.
If the count is less than the given nth occurrence, return -1.
Else, use a loop to find the nth occurrence of the substring and return its index.
Python3
def find_nth_occurrence_1(s, sub, n): count = s.count(sub) if count < n: return -1 else: index = -1 for i in range(n): index = s.find(sub, index+1) return indexmy_string = "hello world, how are you doing today? I hope you are doing well."my_substring = "doing"my_occurrence = 2result = find_nth_occurrence_1(my_string, my_substring, my_occurrence)print(result) |
53
Time Complexity: O(n)
Auxiliary Space: O(1)
METHOD 6: Using loop and counter
APPROACH:
This Approach tells how to find the index of the nth occurrence of a given substring within a given string. The approach used is a simple iteration over the string and checking whether the current substring matches the given substring. If it does, then the occurrence count is incremented. Once the count reaches the desired occurrence, the current index is returned. If no nth occurrence is found, then the function returns -1.
ALGORITHM:
1.Initialize counter as 0
2.Using a loop, search for the substring in the given string, and increase the counter every time the substring is found
3.If the counter is equal to the required occurrence, return the index of the last found substring
4.If the substring is not found enough times, return -1
Python3
def find_nth_occurrence(ini_str, substr, occurrence): count = 0 for i in range(len(ini_str)): if ini_str[i:i+len(substr)] == substr: count += 1 if count == occurrence: return i return -1ini_str = "abababababab"substr = "ab"occurrence = 4print(find_nth_occurrence(ini_str, substr, occurrence)) |
6
Time complexity: O(n*m) where n is the length of the initial string and m is the length of the substring
Auxiliary Space: O(1)
