Given two strings S and W of sizes N and M respectively, the task is to remove the last occurrence of W from S. If there is no occurrence of W in S, print S as it is.
Examples:
Input: S = “This is GeeksForGeeks”, W=”Geeks”
Output: This is GeeksFor
Explanation:
The last occurrence of “Geeks” in the string is substring over the range [16, 20].Input: S=”Hello World”, W=”Hell”
Output: o World
Explanation:
The last occurrence of “Hell” in the string is substring over the range [0, 3].
Approach: The problem can be solved by iterating over every index i of string S and checking if there is a substring starting from the index i, which is equal to string W. Follow the steps below to solve the problem:
- If N is smaller than M, print S, as there can be no occurrence of W in S.
- Initialize a variable i as N-M to iterate over the string S.
- Iterate until i is greater than 0 and perform the following steps:
- Check whether the substring over the range [i, i+M-1] is equal to string W or not. If it is equal, then remove the substring over the range [i, i+M-1] from string S and then break.
- Otherwise, continue.
- Finally, after completing the above steps, print the string S as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to remove last occurrence// of W from Sstring removeLastOccurrence(string S, string W, int N, int M){ // If M is greater than N if (M > N) return S; // Iterate while i is greater than // or equal to 0 for (int i = N - M; i >= 0; i--) { // Stores if occurrence of W has // been found or not int flag = 0; // Iterate over the range [0, M] for (int j = 0; j < M; j++) { // If S[j+1] is not equal to // W[j] if (S[j + i] != W[j]) { // Mark flag true and break flag = 1; break; } } // If occurrence has been found if (flag == 0) { // Delete the substring over the // range [i, i+M] for (int j = i; j < N - M; j++) S[j] = S[j + M]; // Resize the string S S.resize(N - M); break; } } // Return S return S;}// Driver Codeint main(){ // Input string S = "This is GeeksForGeeks"; string W = "Geeks"; int N = S.length(); int M = W.length(); // Function call cout << removeLastOccurrence(S, W, N, M) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to remove last occurrence// of W from Sstatic String removeLastOccurrence(String S, String W, int N, int M){ // If M is greater than N char[] ch = S.toCharArray(); if (M > N) return S; // Iterate while i is greater than // or equal to 0 for(int i = N - M; i >= 0; i--) { // Stores if occurrence of W has // been found or not int flag = 0; // Iterate over the range [0, M] for(int j = 0; j < M; j++) { // If S[j+1] is not equal to // W[j] if (ch[j + i] != W.charAt(j)) { // Mark flag true and break flag = 1; break; } } // If occurrence has been found if (flag == 0) { // Delete the substring over the // range [i, i+M] for(int j = i; j < N - M; j++) ch[j] = ch[j + M]; break; } } char[] chh = new char[N - M]; // Resize the string S for(int i = 0; i < N - M; i++) { chh[i] = ch[i]; } // Return S return String.valueOf(chh);}// Driver Codepublic static void main(String[] args){ // Input String S = "This is GeeksForGeeks"; String W = "Geeks"; int N = S.length(); int M = W.length(); // Function call System.out.print(removeLastOccurrence(S, W, N, M));}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to remove last occurrence# of W from Sdef removeLastOccurrence(S, W, N, M): S = [i for i in S] W = [i for i in W] # If M is greater than N if (M > N): return S # Iterate while i is greater than # or equal to 0 for i in range(N - M, -1, -1): # of W has # been found or not flag = 0 # Iterate over the range [0, M] for j in range(M): # If S[j+1] is not equal to # W[j] if (S[j + i] != W[j]): # Mark flag true and break flag = 1 break # If occurrence has been found if (flag == 0): # Delete the subover the # range [i, i+M] for j in range(i,N-M): S[j] = S[j + M] # Resize the S S = S[:N - M] break # Return S return "".join(S) # Driver Codeif __name__ == '__main__': # Input S = "This is GeeksForGeeks" W = "Geeks" N = len(S) M = len(W) # Function call print (removeLastOccurrence(S, W, N, M))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to remove last occurrence// of W from Sstatic string removeLastOccurrence(string S, string W, int N, int M){ // If M is greater than N char[] ch = S.ToCharArray(); if (M > N) return S; // Iterate while i is greater than // or equal to 0 for (int i = N - M; i >= 0; i--) { // Stores if occurrence of W has // been found or not int flag = 0; // Iterate over the range [0, M] for (int j = 0; j < M; j++) { // If S[j+1] is not equal to // W[j] if (ch[j + i] != W[j]) { // Mark flag true and break flag = 1; break; } } // If occurrence has been found if (flag == 0) { // Delete the substring over the // range [i, i+M] for (int j = i; j < N - M; j++) ch[j] = ch[j + M]; // Resize the string S Array.Resize(ref ch,N - M); break; } } S = string.Concat(ch); // Return S return S;}// Driver Codepublic static void Main(){ // Input string S = "This is GeeksForGeeks"; string W = "Geeks"; int N = S.Length; int M = W.Length; // Function call Console.Write(removeLastOccurrence(S, W, N, M));}}// This code is contributed by bgangwar59. |
Javascript
<script>// JavaScript program for the above approach// Function to remove last occurrence// of W from Sfunction removeLastOccurrence(S, W, N, M){ // If M is greater than N if (M > N) return S; // Iterate while i is greater than // or equal to 0 for (let i = N - M; i >= 0; i--) { // Stores if occurrence of W has // been found or not let flag = 0; // Iterate over the range [0, M] for (let j = 0; j < M; j++) { // If S[j+1] is not equal to // W[j] if (S[j + i] != W[j]) { // Mark flag true and break flag = 1; break; } } // If occurrence has been found if (flag == 0) { // Delete the substring over the // range [i, i+M] for (let j = i; j < N - M; j++) S[j] = S[j + M]; // Resize the string S S = S.substring(0,N - M); break; } } // Return S return S;}// Driver Code// Inputlet S = "This is GeeksForGeeks";let W = "Geeks";let N = S.length;let M = W.length;// Function calldocument.write(removeLastOccurrence(S, W, N, M),"</br>");// This code is contributed by shinjanpatra</script> |
Output
This is GeeksFor
Time Complexity: O(M*N)
Auxiliary Space: O(1)
Approach:
To find the position of the last occurrence of W in S, we can use the rfind() function. This function returns the position of the last occurrence of the specified string in the calling string object. If the specified string is not found, the function returns string::npos, which is a constant value representing an invalid position or index.
Once we have the position of the last occurrence of W in S, we can use the erase() function to remove the substring containing W from S. The erase() function takes two arguments – the starting position from where the substring needs to be erased and the length of the substring to be erased.
If the string W is not present in S, the rfind() function will return string::npos, indicating that W is not present in S. In this case, we can simply return S as it is.
- Use the rfind() function to find the position of the last occurrence of string W in string S.
- If the string W is not present in S, return S as it is.
- If W is found in S, remove the substring containing W from S using the erase() function.
- Return the modified string S.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to remove last occurrence of W from Sstring removeLastOccurrence(string S, string W, int N, int M){ // Find the position of the last occurrence of W in S int pos = S.rfind(W); // If W is not found in S, return S as it is if (pos == string::npos) return S; // Remove the substring containing W from S S.erase(pos, M); return S;}// Driver Codeint main(){ // Input string S = "This is GeeksForGeeks"; string W = "Geeks"; int N = S.length(); int M = W.length(); // Function call cout << removeLastOccurrence(S, W, N, M) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to remove last occurrence of W from S public static String removeLastOccurrence(String S, String W, int N, int M) { // Find the position of the last occurrence of W in // S int pos = S.lastIndexOf(W); // If W is not found in S, return S as it is if (pos == -1) return S; // Remove the substring containing W from S StringBuilder sb = new StringBuilder(S); sb.delete(pos, pos + M); return sb.toString(); } // Driver Code public static void main(String[] args) { // Input String S = "This is GeeksForGeeks"; String W = "Geeks"; int N = S.length(); int M = W.length(); // Function call System.out.println( removeLastOccurrence(S, W, N, M)); }} |
Python3
def remove_last_occurrence(S, W): # Find the position of the last occurrence of W in S pos = S.rfind(W) # If W is not found in S, return S as it is if pos == -1: return S # Remove the substring containing W from S S = S[:pos] + S[pos + len(W):] return S# Driver Codeif __name__ == "__main__": # Input S = "This is GeeksForGeeks" W = "Geeks" # Function call print(remove_last_occurrence(S, W)) |
C#
using System;class Program{ // Function to remove last occurrence of W from S static string RemoveLastOccurrence(string S, string W) { // Find the position of the last occurrence of W in S int pos = S.LastIndexOf(W); // If W is not found in S, return S as it is if (pos == -1) return S; // Remove the substring containing W from S S = S.Remove(pos, W.Length); return S; } static void Main() { // Input string S = "This is GeeksForGeeks"; string W = "Geeks"; // Function call Console.WriteLine(RemoveLastOccurrence(S, W)); }} |
Javascript
// Function to remove last occurrence of W from Sfunction removeLastOccurrence(S, W) { // Find the position of the last occurrence of W in S const pos = S.lastIndexOf(W); // If W is not found in S, return S as it is if (pos === -1) return S; // Remove the substring containing W from S const sb = S.slice(0, pos) + S.slice(pos + W.length); return sb;}// Driver Codefunction main() { // Input const S = "This is GeeksForGeeks"; const W = "Geeks"; // Function call console.log(removeLastOccurrence(S, W));}// Call the main functionmain(); |
Output
This is GeeksFor
Time Complexity: O(N), where N is the length of string S.
Space Complexity: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
