Python | Find last occurrence of substring

Sometimes, while working with strings, we need to find if a substring exists in the string. This problem is quite common and its solution has been discussed many times before. The variation of getting the last occurrence of the string is discussed here. Let’s discuss certain ways in which we can find the last occurrence of substring in string in Python. 

Using rindex() to find last occurrence of substring

rindex() method returns the last occurrence of the substring if present in the string. The drawback of this function is that it throws the exception if there is no substring in the string and hence breaks the code. 

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Using rfind() to find last occurrence of substring

rfind() is the alternate method to perform this task. The advantage that this function offers better than the above method is that, this function returns a “-1” if a substring is not found rather than throwing the error. 

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Using lambda() with rlocate() function

Here we are using the more_itertools library that provides us with rlocate() function that helps us to find the last occurrence of the substring in the given string.

Output:

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Using find() and replace() methods

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Time Complexity: O(n), where n is length of test_string.

Auxiliary Space: O(1)

Using the re module:

The re (regular expression) module in Python allows you to search for patterns in strings. In this approach, we use the finditer function from the re module to find all occurrences of the substring in the string. The finditer function returns an iterator yielding MatchObject instances that have information about the search, such as the start and end indices of the match.

We can then use a for loop to iterate through the matches and keep track of the index of the last occurrence by updating the last_occurrence variable whenever we find a match. Finally, we print the index of the last occurrence.

Index of last occurrence of substring is: 28

Time complexity: O(n), where n is the length of the string
Auxiliary Space : O(n)

Using reversed() function and index()

Step-by-step approach:

1. Reverse the test_string and tar_word
2. Use the index() method to get the first occurrence of the reversed tar_word in the reversed test_string.
3. Calculate the index of the last occurrence of the tar_word by subtracting the index from the length of the test_string and the length of the tar_word.

Index of last occurrence of substring is : 28

Time complexity: O(n) where n is the length of the string
Space complexity: O(1)

Using the numpy:

Algorithm:

1. Initialize the test string and target word.
2. Create an empty numpy array to store the indices of all occurrences of the target word.
3. Iterate over all possible substrings of length equal to the length of the target word in the test string. For each substring, check if it matches the target word or not. If the substring matches the target word, append the index of the first character of the substring to the numpy array.
4. Check if any occurrences of the target word were found or not. If the numpy array is not empty, set the result to be the last element of the array (i.e., the index of the last occurrence of the target word in the test string). Otherwise, set the result to -1 (indicating that the target word was not found in the test string).
5. Print the original string and the index of the last occurrence of the target word (or -1 if the target word was not found).

Below is the implementation of the above approach:

Output:

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Time Complexity: O(n * m), where n is the length of the test string and m is the length of the target word. This is because the list comprehension iterates over all possible substrings of length m in the test string, which takes O(n * m) time in the worst case.

Space Complexity: O(k), where k is the number of occurrences of the target word in the test string. This is because the indices of all occurrences of the target word are stored in a numpy array, which takes O(k) space. The rest of the variables used in the code take constant space.

Using rpartition() method

• Define the string and target word to find last occurrence of substring.
• Use the rpartition() method to split the string at the last occurrence of the target word.
• If the length of split list is 1, print that the substring was not found in the string.
• Otherwise, calculate the index of the last occurrence of the target word using the length of the original string, the length of the third element in the split list (which contains the characters after the last occurrence of the target word), and the length of the target word.
• Print the index of the last occurrence of the target word.

The original string : GfG is best for CS and also best for Learning
Index of last occurrence of substring is : 28

Time Complexity: O(n), where n is the length of the input string.

Auxiliary Space: O(1), as no extra is used.