Wenn Sie bei einer Zeichenfolge alle „b“ und „ac“ in der Zeichenfolge entfernen, müssen Sie sie an Ort und Stelle ersetzen, und Sie dürfen die Zeichenfolge nur einmal durchlaufen. (Quelle Google-Interviewfrage )

Beispiele:

acbac   ==>  ""
aaac    ==>  aa
ababac  ==>   aa
bbbbd   ==>   d

Wir empfehlen dringend, dass Sie hier klicken und es üben, bevor Sie mit der Lösung fortfahren.


Die beiden Bedingungen sind:
1. Das Filtern aller 'b' und 'ac' sollte in einem Durchgang erfolgen
. 2. Kein zusätzlicher Platz erlaubt.

Der Ansatz besteht darin, zwei Indexvariablen i und j zu verwenden. Wir bewegen uns im String mit 'i' fort und fügen Zeichen mit dem Index j außer 'b' und 'ac' hinzu. Der Trick dabei ist, wie man 'a' vor 'c' verfolgt. Ein interessanter Ansatz ist die Verwendung einer Maschine mit zwei Zuständen. Der Zustand wird auf ZWEI gehalten, wenn das vorherige Zeichen 'a' ist, andernfalls ist der Zustand EINS.
1) Wenn Zustand EINS ist, dann kopiere das aktuelle Zeichen NICHT zur Ausgabe, wenn eine der folgenden Bedingungen zutrifft
… a) Aktuelles Zeichen ist „b“ (wir müssen „b“ entfernen)
… b) Aktuelles Zeichen ist „a ' (Das nächste Zeichen kann ein 'c' sein)
2)Wenn der Zustand ZWEI ist und das aktuelle Zeichen nicht 'c' ist, müssen wir zuerst sicherstellen, dass wir das vorherige Zeichen 'a' kopieren. Dann prüfen wir das aktuelle Zeichen, wenn das aktuelle Zeichen nicht 'b' und nicht 'a' ist, dann kopieren wir es zur Ausgabe.

C++

// A C++ program to remove "b" and 'ac' from input string
#include <iostream>
using namespace std;
#define ONE 1
#define TWO 2
  
// The main function that removes occurrences of "a" and "bc"
// in input string
void stringFilter(char *str)
{
    // state is initially ONE (The previous character is not a)
    int state = ONE;
  
    // i and j are index variables, i is used to read next
    // character of input string, j is used for indexes of output
    // string (modified input string)
    int j = 0;
  
    // Process all characters of input string one by one
    for (int i = 0; str[i] != '\0'; i++)
    {
        /* If state is ONE, then do NOT copy the current character
          to output if one of the following conditions is true
           ...a) Current character is 'b' (We need to remove 'b')
           ...b) Current character is 'a' (Next character may be 'c') */
        if (state == ONE && str[i] != 'a' && str[i] != 'b')
        {
            str[j] = str[i];
            j++;
        }
  
        // If state is TWO and current character is not 'c' (other-
        // wise we ignore both previous and current characters)
        if (state == TWO && str[i] != 'c')
        {
            // First copy the previous 'a'
            str[j] = 'a';
            j++;
  
            // Then copy the current character if it is not 'a'
            // and 'b'
            if (str[i] != 'a' && str[i] != 'b')
            {
                str[j] = str[i];
                j++;
            }
        }
  
        // Change state according to current character
        state = (str[i] == 'a')? TWO: ONE;
    }
  
    // If last character was 'a', copy it to output
    if (state == TWO)
    {
        str[j] = 'a';
        j++;
    }
  
    // Set the string terminator
    str[j] = '\0';
}
  
/* Driver program to check above functions */
int main()
{
    char str1[] = "ad";
    stringFilter(str1);
    cout << str1 << endl;
  
    char str2[] = "acbac";
    stringFilter(str2);
    cout << str2 << endl;
  
    char str3[] = "aaac";
    stringFilter(str3);
    cout << str3 << endl;
  
    char str4[] = "react";
    stringFilter(str4);
    cout << str4 << endl;
  
    char str5[] = "aa";
    stringFilter(str5);
    cout << str5 << endl;
  
    char str6[] = "ababaac";
    stringFilter(str6);
    cout << str6 << endl;
  
    return 0;
}

Java

// A Java program to remove "b" and
// 'ac' from input String
import java.util.*;
  
class GFG
{
static final int ONE = 1;
static final int TWO = 2;
  
// The main function that removes occurrences
// of "a" and "bc" in input String
static char[] StringFilter(char []str)
{
    // state is initially ONE
    // (The previous character is not a)
    int state = ONE;
  
    // i and j are index variables,
    // i is used to read next
    // character of input String,
    // j is used for indexes of output
    // String (modified input String)
    int j = 0;
  
    // Process all characters of 
    // input String one by one
    for (int i = 0; i < str.length; i++)
    {
        /* If state is ONE, then do NOT copy 
        the current character to output if 
        one of the following conditions is true
        ...a) Current character is 'b'
              (We need to remove 'b')
        ...b) Current character is 'a' 
              (Next character may be 'c') */
        if (state == ONE && str[i] != 'a' && 
                            str[i] != 'b')
        {
            str[j] = str[i];
            j++;
        }
  
        // If state is TWO and current character 
        // is not 'c' (otherwise we ignore both 
        // previous and current characters)
        if (state == TWO && str[i] != 'c')
        {
            // First copy the previous 'a'
            str[j] = 'a';
            j++;
  
            // Then copy the current character 
            // if it is not 'a' and 'b'
            if (str[i] != 'a' && str[i] != 'b')
            {
                str[j] = str[i];
                j++;
            }
        }
  
        // Change state according to current character
        state = (str[i] == 'a') ? TWO : ONE;
    }
  
    // If last character was 'a',
    // copy it to output
    if (state == TWO)
    {
        str[j] = 'a';
        j++;
    }
    return Arrays.copyOfRange(str, 0, j);
}
  
// Driver Code
public static void main(String[] args)
{
    char str1[] = "ad".toCharArray();
    str1 = StringFilter(str1);
    System.out.print(String.valueOf(str1) + "\n");
  
    char str2[] = "acbac".toCharArray();
    str2 = StringFilter(str2);
    System.out.print(String.valueOf(str2) + "\n");
  
    char str3[] = "aaac".toCharArray();
    str3 = StringFilter(str3);
    System.out.print(String.valueOf(str3) + "\n");
  
    char str4[] = "react".toCharArray();
    str4 = StringFilter(str4);
    System.out.print(String.valueOf(str4) + "\n");
  
    char str5[] = "aa".toCharArray();
    str5 = StringFilter(str5);
    System.out.print(String.valueOf(str5) + "\n");
  
    char str6[] = "ababaac".toCharArray();
    str6 = StringFilter(str6);
    System.out.print(String.valueOf(str6) + "\n");
}
}
  
// This code is contributed by 29AjayKumar

Python

# A Python program to remove "b" and 'ac' from input string
ONE = 1
TWO = 2
  
# Utility function to convert string to list
def toList(string):
    l = []
    for x in string:
        l.append(x)
    return l
  
# Utility function to convert list to string
def toString(l):
    return ''.join(l)
  
# The main function that removes occurrences of "a" and "bc"
# in input string
def stringFilter(string):
  
    # state is initially ONE (The previous character is not a)
    state = ONE
  
    # i and j are index variables, i is used to read next
    # character of input string, j is used for indexes of
    # output string (modified input string)
    j = 0
  
    # Process all characters of input string one by one
    for i in xrange(len(string)):
  
        # If state is ONE, then do NOT copy the current character
        # to output if one of the following conditions is true
        # ...a) Current character is 'b' (We need to remove 'b')
        # ...b) Current character is 'a' (Next character may be 'c')
        if state == ONE and string[i] != 'a' and string[i] != 'b':
            string[j] = string[i]
            j += 1
  
        # If state is TWO and current character is not 'c' (other-
        # wise we ignore both previous and current characters)
        if state == TWO and string[i] != 'c':
            # First copy the previous 'a'
            string[j] = 'a'
            j += 1
  
            # Then copy the current character if it is not 'a' and 'b'
            if string[i] != 'a' and string[i] != 'b':
                string[j] = string[i]
                j += 1
  
        # Change state according to current character
         state = TWO if string[i] == 'a' else ONE
  
    # If last character was 'a', copy it to output
    if state == TWO:
        string[j] = 'a'
        j += 1
  
    return toString(string[:j])
  
# Driver program
string1 = stringFilter(toList("ad"))
print string1
  
string2 = stringFilter(toList("acbac"))
print string2
  
string3 = stringFilter(toList("aaac"))
print string3
  
string4 = stringFilter(toList("react"))
print string4
  
string5 = stringFilter(toList("aa"))
print string5
  
string6 = stringFilter(toList("ababaac"))
print string6
  
# This code is contributed by BHAVYA JAIN

C#

// A C# program to remove "b" and
// 'ac' from input String
using System;
  
class GFG
{
static readonly int ONE = 1;
static readonly int TWO = 2;
  
// The main function that removes occurrences
// of "a" and "bc" in input String
static char[] StringFilter(char []str)
{
      
    // state is initially ONE
    // (The previous character is not a)
    int state = ONE;
  
    // i and j are index variables,
    // i is used to read next
    // character of input String,
    // j is used for indexes of output
    // String (modified input String)
    int j = 0;
  
    // Process all characters of 
    // input String one by one
    for (int i = 0; i < str.Length; i++)
    {
        /* If state is ONE, then do NOT copy 
        the current character to output if 
        one of the following conditions is true
        ...a) Current character is 'b'
            (We need to remove 'b')
        ...b) Current character is 'a' 
            (Next character may be 'c') */
        if (state == ONE && str[i] != 'a' && 
                            str[i] != 'b')
        {
            str[j] = str[i];
            j++;
        }
  
        // If state is TWO and current character 
        // is not 'c' (otherwise we ignore both 
        // previous and current characters)
        if (state == TWO && str[i] != 'c')
        {
            // First copy the previous 'a'
            str[j] = 'a';
            j++;
  
            // Then copy the current character 
            // if it is not 'a' and 'b'
            if (str[i] != 'a' && str[i] != 'b')
            {
                str[j] = str[i];
                j++;
            }
        }
  
        // Change state according to
        // current character
        state = (str[i] == 'a') ? TWO : ONE;
    }
  
    // If last character was 'a',
    // copy it to output
    if (state == TWO)
    {
        str[j] = 'a';
        j++;
    }
    return String.Join("", str).
           Substring(0, j).ToCharArray();
}
  
// Driver Code
public static void Main(String[] args)
{
    char []str1 = "ad".ToCharArray();
    str1 = StringFilter(str1);
    Console.Write(String.Join("", str1) + "\n");
  
    char []str2 = "acbac".ToCharArray();
    str2 = StringFilter(str2);
    Console.Write(String.Join("", str2) + "\n");
  
    char []str3 = "aaac".ToCharArray();
    str3 = StringFilter(str3);
    Console.Write(String.Join("", str3) + "\n");
  
    char []str4 = "react".ToCharArray();
    str4 = StringFilter(str4);
    Console.Write(String.Join("", str4) + "\n");
  
    char []str5 = "aa".ToCharArray();
    str5 = StringFilter(str5);
    Console.Write(String.Join("", str5) + "\n");
  
    char []str6 = "ababaac".ToCharArray();
    str6 = StringFilter(str6);
    Console.Write(String.Join("", str6) + "\n");
}
}
  
// This code is contributed by Rajput-Ji
Ausgabe: 
ad

aa
ret
aa
aaa

Eine Erweiterung des obigen Problems, bei der wir „ac“ überhaupt nicht in der Ausgabe haben wollen:
Der obige Code sieht gut aus und scheint alle Fälle zu behandeln, aber was ist, wenn die Eingabezeichenfolge „aacacc“ ist, erzeugt der obige Code eine Ausgabe als „ac“. was richtig aussieht, da es aufeinanderfolgende Vorkommen von 'a' und 'c' entfernt. Was ist, wenn die Anforderung darin besteht, überhaupt kein „ac“ in der Ausgabezeichenfolge zu haben? Können wir das obige Programm ändern, um eine Ausgabe als leere Zeichenfolge für die Eingabe „aacacc“ und eine Ausgabe als „d“ zu erzeugen, wenn die Eingabe „abcaaccd“ ist? Es stellt sich heraus, dass dies auch mit gegebenen Einschränkungen möglich ist. Die Idee ist einfach. Wir müssen die folgenden Zeilen in die for-Schleife des obigen Programms einfügen.

if (j>1 && str[j-2] == 'a' && str[j-1] =='c')
  j = j-2;

Siehe dies für verschiedene Testfälle des modifizierten Programms.


Eine einfachere Lösung für das ursprüngliche Problem:

C++

// // A C++ program to remove "b" and 'ac' from input string
#include<bits/stdc++.h>
using namespace std;
  
void stringFilter(char *str)
{
    int n = strlen(str);
  
    int i = -1;  // previous character
    int j = 0;   // current character
  
    while (j < n)
    {
        /* check if current and next character forms ac */
        if (j < n-1 && str[j] == 'a' && str[j+1] == 'c')
            j += 2;
  
        /* if current character is b */
        else if (str[j] == 'b')
            j++;
  
        /* if current char is 'c && last char in output
           is 'a' so delete both */
        else if (i >= 0 && str[j] == 'c' && str[i] == 'a')
            i--,j++;
  
        /* else copy curr char to output string */
        else
            str[++i] = str[j++];
    }
    str[++i] = '\0';
}
  
// Driver program to test above function
int main()
{
    char str1[] = "ad";
    cout << "Input => " << str1 << "\nOutput => ";
    stringFilter(str1);
    cout << str1 << endl << endl;
  
    char str2[] = "acbac";
    cout << "Input => " << str2 << "\nOutput => ";
    stringFilter(str2);
    cout << str2 << endl << endl;
  
    char str3[] = "aaac";
    cout << "Input => " << str3 << "\nOutput => ";
    stringFilter(str3);
    cout << str3 << endl << endl;
  
    char str4[] = "react";
    cout << "Input => " << str4 << "\nOutput => ";
    stringFilter(str4);
    cout << str4 << endl << endl;
  
    char str5[] = "aa";
    cout << "Input => " << str5 << "\nOutput => ";
    stringFilter(str5);
    cout << str5 << endl << endl;
  
    char str6[] = "ababaac";
    cout << "Input => " << str6 << "\nOutput => ";
    stringFilter(str6);
    cout << str6 << endl << endl;
  
    char str[] = "abc";
    cout << "Input => " << str << "\nOutput => ";
    stringFilter(str);
    cout << str << endl << endl;
    return 0;
}

Java

// A Java program to remove "b" and 'ac' from input string 
class GfG {
  
// The main function that removes occurrences of "a" and "bc" 
// in input string 
static void stringFilter(char str[]) 
{ 
    int n = str.length; 
    
    int i = -1;  // previous character 
    int j = 0;   // current character 
    
    while (j < n) 
    { 
        /* check if current and next character forms ac */
        if (j < n-1 && str[j] == 'a' && str[j+1] == 'c') 
            j += 2; 
    
        /* if current character is b */
        else if (str[j] == 'b') 
            j++; 
    
        /* if current char is 'c && last char in output 
           is 'a' so delete both */
        else if (i >= 0 && str[j] == 'c' && str[i] == 'a')  {
            i--;
            j++; 
        }
    
        /* else copy curr char to output string */
        else
            str[++i] = str[j++]; 
              
    } 
 System.out.println(new String(str).substring(0,i+1));
} 
  
/* Driver program to check above functions */
public static void main(String[] args) 
{ 
    String str1 = "ad"; 
    stringFilter(str1.toCharArray()); 
  
    String str2 = "acbac"; 
    stringFilter(str2.toCharArray());
  
    String str3 = "aaac"; 
    stringFilter(str3.toCharArray()); 
  
    String str4 = "react"; 
    stringFilter(str4.toCharArray()); 
  
    String str5 = "aa"; 
    stringFilter(str5.toCharArray()); 
  
    String str6 = "ababaac"; 
    stringFilter(str6.toCharArray()); 
}
} 

Python

# A Python program to remove "b" and 'ac' from input string
  
# Utility function to convert string to list
def toList(string):
    l = []
    for x in string:
        l.append(x)
    return l
  
# Utility function to convert list to string
def toString(l):
    return ''.join(l)
  
def stringFilter(string):
  
    # length of string
    n = len(string)
  
    i = -1
    j = 0
  
    while j < n:
  
        # Check if current and next character forms ac
        if j < n-1 and string[j] == 'a' and string[j+1] == 'c':
            j += 2
  
        # If current character is b
        elif string[j] == 'b':
            j += 1
  
        # if current char is 'c && last char in output
        # is 'a' so delete both
        elif i >= 0 and string[j] == 'c' and string[i] == 'a':
            i -= 1
            j += 1
  
        # Else copy curr char to output string
        else:
            i += 1
            string[i] = string[j]
            j += 1
  
    i += 1
    return toString(string[:i])
  
# Driver program
string1 = "ad"
print "Input => " + string1 + "\nOutput => ",
print stringFilter(toList(string1)) + "\n"
  
string2 = "acbac"
print "Input => " + string2 + "\nOutput => ",
print stringFilter(toList(string2)) + "\n"
  
string3 = "aaac"
print "Input => " + string3 + "\nOutput => ",
print stringFilter(toList(string3)) + "\n"
  
string4 = "react"
print "Input => " + string4 + "\nOutput => ",
print stringFilter(toList(string4)) + "\n"
  
string5 = "aa"
print "Input => " + string5 + "\nOutput => ",
print stringFilter(toList(string5)) + "\n"
  
string6 = "ababaac"
print "Input => " + string6 + "\nOutput => ",
print stringFilter(toList(string6)) + "\n"
  
string7 = "abc"
print "Input => " + string7 + "\nOutput => ",
print stringFilter(toList(string7)) + "\n"
  
# This code is contributed by BHAVYA JAIN

C#

// C# program to remove "b" and 'ac' from input string 
using System;
  
class GfG 
{ 
  
    // The main function that removes occurrences of  
    // "a" and "bc" in input string 
    static void stringFilter(char []str) 
    { 
        int n = str.Length; 
        int i = -1; // previous character 
        int j = 0; // current character 
        while (j < n) 
        { 
            /* check if current and next character forms ac */
            if (j < n-1 && str[j] == 'a' && str[j+1] == 'c') 
                j += 2; 
      
            /* if current character is b */
            else if (str[j] == 'b') 
                j++; 
      
            /* if current char is 'c && last char in output 
            is 'a' so delete both */
            else if (i >= 0 && str[j] == 'c' && str[i] == 'a') 
            { 
                i--; 
                j++; 
            } 
      
            /* else copy curr char to output string */
            else
                str[++i] = str[j++]; 
              
        } 
        Console.WriteLine(new String(str)); 
    } 
  
    // Driver Code
    public static void Main() 
    {    
        String str1 = "ad"; 
        stringFilter(str1.ToCharArray()); 
          
        String str2 = "acbac"; 
        stringFilter(str2.ToCharArray()); 
          
        String str3 = "aaac"; 
        stringFilter(str3.ToCharArray()); 
          
        String str4 = "react"; 
        stringFilter(str4.ToCharArray()); 
          
        String str5 = "aa"; 
        stringFilter(str5.ToCharArray()); 
          
        String str6 = "ababaac"; 
        stringFilter(str6.ToCharArray()); 
    } 
} 
  
// This code is contributed by 
//PrinciRaj1992 
Ausgabe: 
Input => ad
Output => ad

Input => acbac
Output =>

Input => aaac
Output => aa

Input => react
Output => ret

Input => aa
Output => aa

Input => ababaac
Output => aaa

Input => abc
Output =>

Vielen Dank an Gaurav Ahirwar für den Vorschlag dieser einfacheren Lösung.

Dieser Artikel wurde von Varun Jain beigesteuert . Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .