Dadas dos strings S y W de tamaños N y M respectivamente, la tarea es eliminar la última aparición de W de S . Si no aparece W en S , imprima S tal como está.
Ejemplos:
Entrada: S = «Esto es GeeksForGeeks», W = «Geeks»
Salida: Esto es GeeksFor
Explicación:
La última aparición de «Geeks» en la string es una substring sobre el rango [16, 20].Entrada: S=”Hello World”, W=”Hell”
Salida: o World
Explicación:
La última aparición de “Hell” en la string es una substring sobre el rango [0, 3].
Enfoque: el problema se puede resolver iterando sobre cada índice i de la string S y verificando si hay una substring que comience desde el índice i , que es igual a la string W. Siga los pasos a continuación para resolver el problema:
- Si N es menor que M , imprima S , ya que W no puede aparecer en S .
- Inicialice una variable i como NM para iterar sobre la string S .
- Iterar hasta que i sea mayor que 0 y realizar los siguientes pasos:
- Compruebe si la substring sobre el rango [i, i+M-1] es igual a la string W o no. Si es igual, elimine la substring sobre el rango [i, i+M-1] de la string S y luego rompa .
- De lo contrario, continúa .
- Finalmente, después de completar los pasos anteriores, imprima la string S como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to remove last occurrence
// of W from S
string 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 Code
int 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 approach
import java.util.*;
class GFG{
// Function to remove last occurrence
// of W from S
static 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 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.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 S def 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 Code if __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 approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to remove last occurrence
// of W from S
static 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 Code
public 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 S
function 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
// Input
let S = "This is GeeksForGeeks";
let W = "Geeks";
let N = S.length;
let M = W.length;
// Function call
document.write(removeLastOccurrence(S, W, N, M),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
This is GeeksFor
Complejidad temporal: O(M*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sameekshakhandelwal1712 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA