Dada una string, elimine recursivamente los caracteres duplicados adyacentes de la string. La string de salida no debe tener duplicados adyacentes. Vea los siguientes ejemplos.
Ejemplos :
Entrada : azxxxzy
Salida : ay
- Primero, “axxxzy” se reduce a “azzy”.
- La string «azzy» contiene duplicados,
- por lo que se reduce aún más a «ay».
Entrada : geeksforgeeg
Salida : gksfor
- Primero, «geeksforgeeg» se reduce a «gksforgg».
- La string «gksforgg» contiene duplicados,
- por lo que se reduce aún más a «gksfor».
Entrada : caaabbbaacdddd
Salida : String vacíaEntrada : acaaabbbacdddd
Salida : acac
Se puede seguir el siguiente enfoque para eliminar duplicados en tiempo O(N) :
- Comience desde el carácter más a la izquierda y elimine los duplicados en la esquina izquierda si hay alguno.
- El primer carácter debe ser diferente de su adyacente ahora. Recur para string de longitud n-1 (string sin primer carácter).
- Deje que la string obtenida después de reducir la substring derecha de longitud n-1 sea rem_str . Hay tres casos posibles
- Si el primer carácter de rem_str coincide con el primer carácter de la string original, elimine el primer carácter de rem_str .
- Si la string restante se vacía y el último carácter eliminado es el mismo que el primer carácter de la string original. Devuelve una string vacía.
- De lo contrario, agregue el primer carácter de la string original al comienzo de rem_str .
- Devuelve rem_str .
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to remove all adjacent duplicates from a string
#include <bits/stdc++.h>
using namespace std;
// Recursively removes adjacent duplicates from str and
// returns new string. last_removed is a pointer to
// last_removed character
char* removeUtil(char* str, char* last_removed)
{
// If length of string is 1 or 0
if (str[0] == '\0' || str[1] == '\0')
return str;
// Remove leftmost same characters and recur for
// remaining string
if (str[0] == str[1]) {
*last_removed = str[0];
while (str[1] && str[0] == str[1])
str++;
str++;
return removeUtil(str, last_removed);
}
// At this point, the first character is definitely
// different from its adjacent. Ignore first character
// and recursively remove characters from remaining
// string
char* rem_str = removeUtil(str + 1, last_removed);
// Check if the first character of the rem_string
// matches with the first character of the original
// string
if (rem_str[0] && rem_str[0] == str[0]) {
*last_removed = str[0];
// Remove first character
return (rem_str + 1);
}
// If remaining string becomes empty and last removed
// character is same as first character of original
// string. This is needed for a string like "acbbcddc"
if (rem_str[0] == '\0' && *last_removed == str[0])
return rem_str;
// If the two first characters of str and rem_str don't
// match, append first character of str before the first
// character of rem_str.
rem_str--;
rem_str[0] = str[0];
return rem_str;
}
// Function to remove
char* remove(char* str)
{
char last_removed = '\0';
return removeUtil(str, &last_removed);
}
// Driver program to test above functions
int main()
{
char str1[] = "geeksforgeeg";
cout << remove(str1) << endl;
char str2[] = "azxxxzy";
cout << remove(str2) << endl;
char str3[] = "caaabbbaac";
cout << remove(str3) << endl;
char str4[] = "gghhg";
cout << remove(str4) << endl;
char str5[] = "aaaacddddcappp";
cout << remove(str5) << endl;
char str6[] = "aaaaaaaaaa";
cout << remove(str6) << endl;
char str7[] = "qpaaaaadaaaaadprq";
cout << remove(str7) << endl;
char str8[] = "acaaabbbacdddd";
cout << remove(str8) << endl;
char str9[] = "acbbcddc";
cout << remove(str9) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to remove all adjacent duplicates from a string
#include <stdio.h>
#include <string.h>
// Recursively removes adjacent duplicates from str and
// returns new string. last_removed is a pointer to
// last_removed character
char* removeUtil(char* str, char* last_removed)
{
// If length of string is 1 or 0
if (str[0] == '\0' || str[1] == '\0')
return str;
// Remove leftmost same characters and recur for
// remaining string
if (str[0] == str[1]) {
*last_removed = str[0];
while (str[1] && str[0] == str[1])
str++;
str++;
return removeUtil(str, last_removed);
}
// At this point, the first character is definitely
// different from its adjacent. Ignore first character
// and recursively remove characters from remaining
// string
char* rem_str = removeUtil(str + 1, last_removed);
// Check if the first character of the rem_string
// matches with the first character of the original
// string
if (rem_str[0] && rem_str[0] == str[0]) {
*last_removed = str[0];
// Remove first character
return (rem_str + 1);
}
// If remaining string becomes empty and last removed
// character is same as first character of original
// string. This is needed for a string like "acbbcddc"
if (rem_str[0] == '\0' && *last_removed == str[0])
return rem_str;
// If the two first characters of str and rem_str don't
// match, append first character of str before the first
// character of rem_str.
rem_str--;
rem_str[0] = str[0];
return rem_str;
}
// Function to remove
char* removes(char* str)
{
char last_removed = '\0';
return removeUtil(str, &last_removed);
}
// Driver program to test above functions
int main()
{
char str1[] = "geeksforgeeg";
printf("%s\n", removes(str1));
char str2[] = "azxxxzy";
printf("%s\n", removes(str2));
char str3[] = "caaabbbaac";
printf("%s\n", removes(str3));
char str4[] = "gghhg";
printf("%s\n", removes(str4));
char str5[] = "aaaacddddcappp";
printf("%s\n", removes(str5));
char str6[] = "aaaaaaaaaa";
printf("%s\n", removes(str6));
char str7[] = "qpaaaaadaaaaadprq";
printf("%s\n", removes(str7));
char str8[] = "acaaabbbacdddd";
printf("%s\n", removes(str8));
char str9[] = "acbbcddc";
printf("%s\n", removes(str9));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to remove all adjacent duplicates from a
// string
import java.io.*;
import java.util.*;
class GFG {
static char last_removed; //will store the last char removed during recursion
// Recursively removes adjacent duplicates from str and
// returns new string. last_removed is a pointer to
// last_removed character
static String removeUtil(String str)
{
// If length of string is 1 or 0
if (str.length() == 0 || str.length() == 1)
return str;
// Remove leftmost same characters and recur for
// remaining string
if (str.charAt(0) == str.charAt(1)) {
last_removed = str.charAt(0);
while (str.length() > 1
&& str.charAt(0) == str.charAt(1))
str = str.substring(1, str.length());
str = str.substring(1, str.length());
return removeUtil(str);
}
// At this point, the first character is definitely
// different from its adjacent. Ignore first
// character and recursively remove characters from
// remaining string
String rem_str
= removeUtil(str.substring(1, str.length()));
// Check if the first character of the rem_string
// matches with the first character of the original
// string
if (rem_str.length() != 0
&& rem_str.charAt(0) == str.charAt(0)) {
last_removed = str.charAt(0);
// Remove first character
return rem_str.substring(1, rem_str.length());
}
// If remaining string becomes empty and last
// removed character is same as first character of
// original string. This is needed for a string like
// "acbbcddc"
if (rem_str.length() == 0
&& last_removed == str.charAt(0))
return rem_str;
// If the two first characters of str and rem_str
// don't match, append first character of str before
// the first character of rem_str
return (str.charAt(0) + rem_str);
}
static String remove(String str)
{
last_removed = '\0';
return removeUtil(str);
}
// Driver code
public static void main(String args[])
{
String str1 = "geeksforgeeg";
System.out.println(remove(str1));
String str2 = "azxxxzy";
System.out.println(remove(str2));
String str3 = "caaabbbaac";
System.out.println(remove(str3));
String str4 = "gghhg";
System.out.println(remove(str4));
String str5 = "aaaacddddcappp";
System.out.println(remove(str5));
String str6 = "aaaaaaaaaa";
System.out.println(remove(str6));
String str7 = "qpaaaaadaaaaadprq";
System.out.println(remove(str7));
String str8 = "acaaabbbacdddd";
System.out.println(remove(str8));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python
# Python program to remove # all adjacent duplicates from a string # Recursively removes adjacent # duplicates from str and returns # new string. last_removed is a # pointer to last_removed character def removeUtil(string, last_removed): # If length of string is 1 or 0 if len(string) == 0 or len(string) == 1: return string # Remove leftmost same characters # and recur for remaining # string if string[0] == string[1]: last_removed = ord(string[0]) while len(string) > 1 and string[0] == string[1]: string = string[1:] string = string[1:] return removeUtil(string, last_removed) # At this point, the first # character is definitely different # from its adjacent. Ignore first # character and recursively # remove characters from remaining string rem_str = removeUtil(string[1:], last_removed) # Check if the first character # of the rem_string matches # with the first character of # the original string if len(rem_str) != 0 and rem_str[0] == string[0]: last_removed = ord(string[0]) return (rem_str[1:]) # If remaining string becomes # empty and last removed character # is same as first character of # original string. This is needed # for a string like "acbbcddc" if len(rem_str) == 0 and last_removed == ord(string[0]): return rem_str # If the two first characters of # str and rem_str don't match, # append first character of str # before the first character of # rem_str. return ([string[0]] + rem_str) def remove(string): last_removed = 0 return toString(removeUtil(toList(string), last_removed)) # Utility functions def toList(string): x = [] for i in string: x.append(i) return x def toString(x): return ''.join(x) # Driver program string1 = "geeksforgeeg" print remove(string1) string2 = "azxxxzy" print remove(string2) string3 = "caaabbbaac" print remove(string3) string4 = "gghhg" print remove(string4) string5 = "aaaacddddcappp" print remove(string5) string6 = "aaaaaaaaaa" print remove(string6) string7 = "qpaaaaadaaaaadprq" print remove(string7) string8 = "acaaabbbacdddd" print remove(string8) string9 = "acbbcddc" print remove(string9) # This code is contributed by BHAVYA JAIN
C#
// C# program to remove
// all adjacent duplicates
// from a string
using System;
class GFG
{
// Recursively removes adjacent
// duplicates from str and returns
// new string. last_removed is a
// pointer to last_removed character
static string removeUtil(string str,
char last_removed)
{
// If length of string is 1 or 0
if (str.Length == 0 || str.Length == 1)
return str;
// Remove leftmost same characters
// and recur for remaining
// string
if (str[0] == str[1])
{
last_removed = str[0];
while (str.Length > 1 && str[0] ==
str[1]) {
str = str.Substring(1, str.Length - 1);
}
str = str.Substring(1, str.Length - 1);
return removeUtil(str, last_removed);
}
// At this point, the first
// character is definitely different
// from its adjacent. Ignore first
// character and recursively
// remove characters from remaining string
string rem_str = removeUtil(str.Substring(
1,str.Length - 1), last_removed);
// Check if the first character of
// the rem_string matches with
// the first character of the original string
if (rem_str.Length != 0 &&
rem_str[0] == str[0])
{
last_removed = str[0];
// Remove first character
return rem_str.Substring(1,rem_str.Length - 1);
}
// If remaining string becomes
// empty and last removed character
// is same as first character of
// original string. This is needed
// for a string like "acbbcddc"
if (rem_str.Length == 0 && last_removed ==
str[0])
return rem_str;
// If the two first characters
// of str and rem_str don't match,
// append first character of str
// before the first character of
// rem_str
return (str[0] + rem_str);
}
static string remove(string str)
{
char last_removed = '\0';
return removeUtil(str, last_removed);
}
// Driver code
public static void Main()
{
string str1 = "geeksforgeeg";
Console.Write(remove(str1) + "\n");
string str2 = "azxxxzy";
Console.Write(remove(str2) + "\n");
string str3 = "caaabbbaac";
Console.Write(remove(str3) + "\n");
string str4 = "gghhg";
Console.Write(remove(str4) + "\n");
string str5 = "aaaacddddcappp";
Console.Write(remove(str5) + "\n");
string str6 = "aaaaaaaaaa";
Console.Write(remove(str6) + "\n");
string str7 = "qpaaaaadaaaaadprq";
Console.Write(remove(str7) + "\n");
string str8 = "acaaabbbacdddd";
Console.Write(remove(str8) + "\n");
string str9 = "acbbcdd";
Console.Write(remove(str9) + "\n");
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Python program to remove
// all adjacent duplicates from a string
// Recursively removes adjacent
// duplicates from str and returns
// new string. last_removed is a
// pointer to last_removed character
function removeUtil(string, last_removed){
// If length of string is 1 or 0
if(string.length == 0 || string.length == 1)
return string
// Remove leftmost same characters
// and recur for remaining
// string
if(string[0] == string[1]){
last_removed = string.charCodeAt(0)
while(string.length > 1 && string[0] == string[1])
string = string.substr(1,)
string = string.substr(1,)
return removeUtil(string, last_removed)
}
// At this point, the first
// character is functioninitely different
// from its adjacent. Ignore first
// character and recursively
// remove characters from remaining string
let rem_str = removeUtil(string.substr(1,), last_removed)
// Check if the first character
// of the rem_string matches
// with the first character of
// the original string
if(rem_str.length != 0 && rem_str[0] == string[0]){
last_removed = string.charCodeAt(0)
return rem_str.substr(1,)
}
// If remaining string becomes
// empty and last removed character
// is same as first character of
// original string. This is needed
// for a string like "acbbcddc"
if(rem_str.length == 0 && last_removed == string.charCodeAt(0))
return rem_str
// If the two first characters of
// str and rem_str don't match,
// push first character of str
// before the first character of
// rem_str.
let res = string[0] + rem_str
return res
}
function remove(string){
let last_removed = 0
return removeUtil(string,last_removed)
}
// Driver program
let string1 = "geeksforgeeg"
document.write(remove(string1),"</br>")
let string2 = "azxxxzy"
document.write(remove(string2),"</br>")
let string3 = "caaabbbaac"
document.write(remove(string3),"</br>")
let string4 = "gghhg"
document.write(remove(string4),"</br>")
let string5 = "aaaacddddcappp"
document.write(remove(string5),"</br>")
let string6 = "aaaaaaaaaa"
document.write(remove(string6),"</br>")
let string7 = "qpaaaaadaaaaadprq"
document.write(remove(string7),"</br>")
let string8 = "acaaabbbacdddd"
document.write(remove(string8),"</br>")
let string9 = "acbbcddc"
document.write(remove(string9),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
gksfor ay g a qrq acac a
Complejidad de tiempo: la complejidad de tiempo de la solución se puede escribir como T(n) = T(nk) + O(k) donde n es la longitud de la string de entrada y k es el número de primeros caracteres que son iguales. La solución de la recurrencia es O(n)
Gracias a Prachi Bodke por sugerir este problema y la solución inicial.
Otro enfoque:
la idea aquí es verificar si String remStr tiene el carácter repetido que coincide con el último carácter de la string principal. Si eso sucede, debemos seguir eliminando ese carácter antes de concatenar string s y string remStr.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
string removeDuplicates(string s, char ch)
{
// If length of string is 1 or 0
if (s.length() <= 1) {
return s;
}
int i = 0;
while (i < s.length()) {
if (i + 1 < s.length() && s[i] == s[i + 1]) {
int j = i;
while (j + 1 < s.length() && s[j] == s[j + 1]) {
j++;
}
char lastChar = i > 0 ? s[i - 1] : ch;
string remStr = removeDuplicates(
s.substr(j + 1, s.length()), lastChar);
s = s.substr(0, i);
int k = s.length(), l = 0;
// Recursively remove all the adjacent
// characters formed by removing the
// adjacent characters
while (remStr.length() > 0 && s.length() > 0
&& remStr[0] == s[s.length() - 1]) {
// Have to check whether this is the
// repeated character that matches the
// last char of the parent String
while (remStr.length() > 0
&& remStr[0] != ch
&& remStr[0] == s[s.length() - 1]) {
remStr
= remStr.substr(1, remStr.length());
}
s = s.substr(0, s.length() - 1);
}
s = s + remStr;
i = j;
}
else {
i++;
}
}
return s;
}
// Driver Code
int main()
{
string str1 = "mississipie";
cout << removeDuplicates(str1, ' ') << endl;
string str2 = "ocvvcolop";
cout << removeDuplicates(str2, ' ') << endl;
}
// This code is contributed by nirajgusain5
Java
// Java Program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
private static String removeDuplicates(
String s, char ch)
{
// If length of string is 1 or 0
if (s == null || s.length() <= 1)
{
return s;
}
int i = 0;
while (i < s.length())
{
if (i + 1 < s.length()
&& s.charAt(i) == s.charAt(i + 1))
{
int j = i;
while (j + 1 < s.length()
&& s.charAt(j) ==
s.charAt(j + 1))
{
j++;
}
char lastChar
= i > 0 ? s.charAt(i - 1) : ch;
String remStr = removeDuplicates(
s.substring(j + 1, s.length()),
lastChar);
s = s.substring(0, i);
int k = s.length(), l = 0;
// Recursively remove all the adjacent
// characters formed by removing the
// adjacent characters
while (remStr.length() > 0 &&
s.length() > 0 &&
remStr.charAt(0) ==
s.charAt(s.length() - 1))
{
// Have to check whether this is the
// repeated character that matches the
// last char of the parent String
while (remStr.length() > 0
&& remStr.charAt(0) != ch
&& remStr.charAt(0)
== s.charAt(s.length()
- 1))
{
remStr = remStr.substring(
1, remStr.length());
}
s = s.substring(0, s.length() - 1);
}
s = s + remStr;
i = j;
}
else
{
i++;
}
}
return s;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "mississipie";
System.out.println(removeDuplicates(
str1, ' '));
String str2 = "ocvvcolop";
System.out.println(removeDuplicates(
str2, ' '));
}
}
// This code is contributed by Niharika Sahai
Python3
# Python Program for above approach # Recursively removes adjacent # duplicates from str and # returns new string. las_removed # is a pointer to # last_removed character def removeDuplicates(s,ch): # If length of string is 1 or 0 if (len(s) <= 1): return s i = 0 while (i < len(s)): if (i + 1 < len(s) and s[i] == s[i + 1]): j = i while (j + 1 < len(s) and s[j] == s[j + 1]): j += 1 lastChar = s[i - 1] if(i > 0) else ch remStr = removeDuplicates(s[j + 1: len(s)], lastChar) s = s[0: i] k,l = len(s), 0 # Recursively remove all the adjacent # characters formed by removing the # adjacent characters while (len(remStr) > 0 and len(s) > 0 and remStr[0] == s[len(s) - 1]): # Have to check whether this is the # repeated character that matches the # last char of the parent String while (len(remStr) > 0 and remStr[0] != ch and remStr[0] == s[len(s) - 1]): remStr = remStr[1: len(remStr)+1] s = s[0: len(s) - 1] s = s + remStr i = j else: i += 1 return s # Driver Code str1 = "mississipie" print(removeDuplicates(str1, ' ')) str2 = "ocvvcolop" print(removeDuplicates(str2, ' ')) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript Program for above approach
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
function removeDuplicates(s,ch)
{
// If length of string is 1 or 0
if (s.length <= 1) {
return s;
}
let i = 0;
while (i < s.length) {
if (i + 1 < s.length && s[i] == s[i + 1]) {
let j = i;
while (j + 1 < s.length && s[j] == s[j + 1]) {
j++;
}
let lastChar = i > 0 ? s[i - 1] : ch;
let remStr = removeDuplicates(
s.substring(j + 1, s.length), lastChar);
s = s.substring(0, i);
let k = s.length, l = 0;
// Recursively remove all the adjacent
// characters formed by removing the
// adjacent characters
while (remStr.length > 0 && s.length > 0
&& remStr[0] == s[s.length - 1]) {
// Have to check whether this is the
// repeated character that matches the
// last char of the parent String
while (remStr.length > 0
&& remStr[0] != ch
&& remStr[0] == s[s.length - 1]) {
remStr
= remStr.substring(1, remStr.length+1);
}
s = s.substring(0, s.length - 1);
}
s = s + remStr;
i = j;
}
else {
i++;
}
}
return s;
}
// Driver Code
let str1 = "mississipie";
console.log(removeDuplicates(str1, ' '));
let str2 = "ocvvcolop";
document.write(removeDuplicates(str2, ' '),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
mpie lop
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA