Reemplace dos substrings (de una string) entre sí

Dadas 3 strings S , A y B . La tarea es reemplazar cada substring de S igual a A con B y cada substring de S igual a B con A . Es posible que dos o más substrings que coincidan con A o B se superpongan. Para evitar confusiones sobre esta situación, debe buscar la substring más a la izquierda que coincida con A o B , reemplazarla y luego continuar con el resto de la string. 
Por ejemplo, al hacer coincidir A = «aa» con S = «aaa» , A[0, 1]tendrá preferencia sobre A[1, 2] . 

Tenga en cuenta que A y B tendrán la misma longitud y A != B .

Ejemplos: 

Entrada: S = “aab”, A = “aa”, B = “bb” 
Salida: bbb 
Hacemos coincidir los dos primeros caracteres con A y reemplazándolos con B obtenemos bbb. 
Luego continuamos con el algoritmo comenzando en el índice 3 y no encontramos más coincidencias.

Entrada: S = «aabbaabb», A = «aa», B = «bb» 
Salida: bbaabbaa 
Reemplazamos todas las apariciones de «aa» con «bb» y «bb» con «aa», por lo que la string resultante es » bbaabbaa”. 
 

Enfoque: revise todas las substrings posibles de S de longitud len(A) . si alguna substring coincide con A o B , actualice la string según sea necesario e imprima la string actualizada al final.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the resultant string
string updateString(string S,
                    string A, string B)
{
 
    int l = A.length();
 
    // Iterate through all positions i
    for (int i = 0; i + l <= S.length(); i++)
    {
 
        // Current sub-string of
        // length = len(A) = len(B)
        string curr = S.substr(i, i + l);
 
        // If current sub-string gets
        // equal to A or B
        if (curr == A)
        {
 
            // Update S after replacing A
            string new_string = "";
            new_string += S.substr(0, i) + B +
                          S.substr(i + l, S.length());
            S = new_string;
            i += l - 1;
        }
        else if(curr == B)
        {
 
            // Update S after replacing B
            string new_string = "";
            new_string += S.substr(0, i) + A +
                          S.substr(i + l, S.length());
            S = new_string;
            i += l - 1;
        }
        else
        {
          //do nothing
        }
    }
 
    // Return the updated string
    return S;
}
 
// Driver code
int main()
{
    string S = "aaxb";
    string A = "aa";
    string B = "bb";
 
    cout << (updateString(S, A, B)) << endl;
}
 
// This code is contributed by
// Surendra_Gangwar

// Java implementation of the approach
class GFG {
 
    // Function to return the resultant string
    static String updateString(String S, String A, String B)
    {
 
        int l = A.length();
 
        // Iterate through all positions i
        for (int i = 0; i + l <= S.length(); i++) {
 
            // Current sub-string of length = len(A) = len(B)
            String curr = S.substring(i, i + l);
 
            // If current sub-string gets equal to A or B
            if (curr.equals(A)) {
 
                // Update S after replacing A
                String new_string
                    = S.substring(0, i)
                      + B + S.substring(i + l, S.length());
                S = new_string;
                i += l - 1;
            }
            else {
 
                // Update S after replacing B
                String new_string
                    = S.substring(0, i)
                      + A + S.substring(i + l, S.length());
                S = new_string;
                i += l - 1;
            }
        }
 
        // Return the updated string
        return S;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String S = "aab";
        String A = "aa";
        String B = "bb";
 
        System.out.println(updateString(S, A, B));
    }
}

# Python3 implementation of the approach
 
# Function to return the resultant string
def updateString(S, A, B):
     
    l = len(A)
     
    # Iterate through all positions i
    i = 0
    while i + l <= len(S):
 
        # Current sub-string of
        # length = len(A) = len(B)
        curr = S[i:i+l]
 
        # If current sub-string gets
        # equal to A or B
        if curr == A:
 
            # Update S after replacing A
            new_string = S[0:i] + B + S[i + l:len(S)]
            S = new_string
            i += l - 1
             
        else:
 
            # Update S after replacing B
            new_string = S[0:i] + A + S[i + l:len(S)]
            S = new_string
            i += l - 1
         
        i += 1
     
    # Return the updated string
    return S
 
# Driver code
if __name__ == "__main__":
     
    S = "aab"
    A = "aa"
    B = "bb"
 
    print(updateString(S, A, B))
     
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the resultant string
    static string updateString(string S, string A, string B)
    {
        int l = A.Length;
 
        // Iterate through all positions i
        for (int i = 0; i + l <= S.Length; i++)
        {
 
            // Current sub-string of length = len(A) = len(B)
            string curr = S.Substring(i, l);
 
            // If current sub-string gets equal to A or B
            if (curr.Equals(A))
            {
 
                // Update S after replacing A
                string new_string = S.Substring(0, i) +
                                 B + S.Substring(i + l);
                S = new_string;
                i += l - 1;
            }
            else
            {
 
                // Update S after replacing B
                string new_string = S.Substring(0, i) +
                                A + S.Substring(i + l);
                S = new_string;
                i += l - 1;
            }
        }
 
        // Return the updated string
        return S;
    }
 
    // Driver code
    public static void Main()
    {
        string S = "aab";
        string A = "aa";
        string B = "bb";
        Console.WriteLine(updateString(S, A, B));
    }
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
// Function to return the resultant string
function updateString($S, $A, $B)
{
 
    $l = strlen($A);
 
    // Iterate through all positions i
    for ($i = 0; $i + $l <= strlen($S); $i++)
    {
 
        // Current sub-string of length = len(A) = len(B)
        $curr = substr($S, $i, $i + $l);
 
        // If current sub-string gets equal to A or B
        if (strcmp($curr, $A) == 0)
        {
 
            // Update S after replacing A
            $new_string = substr($S, 0, $i) . $B .
                        substr($S, $i + $l, strlen($S));
            $S = $new_string;
            $i += $l - 1;
        }
        else
        {
 
            // Update S after replacing B
            $new_string = substr($S, 0, $i) . $A .
                        substr($S, $i + $l, strlen($S));
            $S = $new_string;
            $i += $l - 1;
        }
    }
 
    // Return the updated string
    return $S;
}
 
// Driver code
$S = "aab";
$A = "aa";
$B = "bb";
 
echo(updateString($S, $A, $B));
 
// This code is contributed by Code_Mech.

<script>
 
// Javascript implementation of the approach
 
// Function to return the resultant string
function updateString(S, A, B)
{
    let l = A.length;
 
    // Iterate through all positions i
    for(let i = 0; i + l <= S.length; i++)
    {
         
        // Current sub-string of length = len(A) = len(B)
        let curr = S.substring(i, i + l);
 
        // If current sub-string gets equal to A or B
        if (curr == A)
        {
             
            // Update S after replacing A
            let new_string = S.substring(0, i) +
                         B + S.substring(i + l);
            S = new_string;
            i += l - 1;
        }
        else
        {
             
            // Update S after replacing B
            let new_string = S.substring(0, i) +
                         A + S.substring(i + l);
            S = new_string;
            i += l - 1;
        }
    }
 
    // Return the updated string
    return S;
}
 
// Driver code
let S = "aab";
let A = "aa";
let B = "bb";
 
document.write(updateString(S, A, B));
 
// This code is contributed by mukesh07
 
</script>

bbb

Complejidad de tiempo: O(n*n), ya que la función substr se usa dentro del ciclo
Espacio auxiliar: O(n)