Python – Extract String after Nth occurrence of K character

Given a String, extract the string after Nth occurrence of a character. 

Input : test_str = ‘geekforLazyroar’, K = “e”, N = 2 
Output : kforLazyroar 
Explanation : After 2nd occur. of “e” string is extracted. 

Input : test_str = ‘geekforLazyroar’, K = “e”, N = 4 
Output : ks 
Explanation : After 4th occur. of “e” string is extracted.

Method #1 : Using split()

This is one of the ways in which this task can be performed. In this we customize split() to split on Nth occurrence and then print the rear extracted string using “-1”.

The original string is : geekforLazyroar
The extracted string : eks

Time complexity: O(n), where n is the length of the input string.
Auxiliary space: O(n).

Method #2 : Using re.split()

This is yet another way to solve this problem. Similar to above function, we perform split() to perform task of splitting but from regex library which also provides flexibility to split on Nth occurrence.

The original string is : geekforLazyroar
The extracted string : eks

Time Complexity: O(n), where n is the length of the input string ‘test_str’. 
Auxiliary Space: O(n), where n is the length of the input string ‘test_str’. 

Method #3 : Using slicing

The original string : neveropen
The extracted string : ksforLazyroar

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 4: Using try-except and index()

1. Define a function named extract_string that takes three arguments, a test string (test_str), a character (K) and an integer (N).
2. Initialize a variable named index with value 0.
3. Loop through the range of N using a for loop:
   a. Inside the for loop, use the index() method on test_str with K and index as the starting index to get the index of Nth occurrence of K.
   b. Update the value of index with the index of Nth occurrence of K + 1.
4. Use slicing to extract the string after Nth occurrence of K and return it.
5. If there are not enough occurrences of K in the string, the index() method will raise a ValueError. Catch the exception using a try-except block.
6. If the exception is caught, return -1.

The extracted string : kforLazyroar

Time Complexity: O(N*K), where N is the value of N and K is the average length of the substring between two occurrences of K in the test_str. The loop runs N times and, in each iteration, it searches for the next occurrence of K in the substring of test_str, which has an average length of K.

Auxiliary Space: O(1), which means it uses a constant amount of extra memory to execute. This is because the algorithm only stores the index of Nth occurrence of K and the extracted substring in memory, and these variables have constant size regardless of the input size.

 Method #5: Using the string method find() and string slicing.

1-Initialize the input string test_str, the character to find K, and the Nth occurrence N.
2-Initialize a variable index to 0 and a variable count to 0.
3-While count is less than N:
  a. Find the index of the K character in test_str starting from the index position using the find()      method.
  b. If the find() method returns -1, exit the loop.
  c. Otherwise, increment count by 1 and update the value of index to index + 1.
4-Extract the substring from test_str starting from the index position to the end of the string using slicing.
5-Print the extracted substring.

The original string is : geekforLazyroar
The extracted string : eks

Time complexity: O(N * M), where N is the value of N and M is the length of the input string test_str. 
Auxiliary space: O(1), as the program uses only a constant amount of extra memory to store the variables index, K, N, and res..

Method #6: Using for loop and slicing

Step-by-step approach:

• Find all occurrences (indices) of K in string using for loop
• Slice the string 3rd occurrence index to end
• Display the sliced string

Below is the implementation of the above approach:

The original string is : geekforLazyroar
The extracted string : eeks

Time Complexity : O(N)
Auxiliary Space : O(1)

Method 7 : Using List Comprehension and Enumerate()

Initialize the test string.
Initialize the K character and N value.
Use list comprehension to iterate over the string and store the index of each occurrence of the K character.
Use the enumerate() function to iterate over the list of indices and select the index of the Nth occurrence of the K character.
Use slicing to extract the string after the matched K character.
If the Nth occurrence of the K character is not found, print an error message.

The original string is : geekforLazyroar
The extracted string : eks

Time complexity: O(n), where n is the length of the string.
Auxiliary space: O(m), where m is the number of occurrences of the K character in the string.