Recuento de strings que se vuelven iguales a una de las dos strings después de una eliminación

Dadas dos strings str1 y str2 , la tarea es contar todas las strings válidas. A continuación se muestra un ejemplo de una string válida: 
If str1 = «toy» and str2 = «try» . Entonces S = «tory» es una string válida porque cuando se elimina un solo carácter, es decir, S = «t o ry» = «try» se vuelve igual a str1 . Esta propiedad también debe ser válida con str2 , es decir, S = “to r y” = “toy” = str2. 
La tarea es imprimir el recuento de todas las posibles strings válidas.
Ejemplos: 
 

Entrada: str = “juguete”, str2 = “probar” 
Salida: 2 
Las dos palabras dadas pueden obtenerse de la palabra “t o y” o de la palabra “t ro y”. Entonces la salida es 2.
Entrada: str1 = «dulce», str2 = «oveja» 
Salida: 0 
Las dos palabras dadas no se pueden obtener de la misma palabra quitando una letra. 
 

Enfoque: Calcule A como el prefijo común más largo de str1 y str2 y C como el sufijo común más largo de str1 y str2 . Si ambas strings son iguales, entonces son posibles 26 * (n + 1) strings. De lo contrario, establezca count = 0 y l igual al primer índice que no forma parte del prefijo común y r es el índice más a la derecha que no forma parte del sufijo común. 
Ahora, si str1[l+1 … r] = str2[l … r-1] entonces actualice count = count + 1 . 
Y si str1[l… r-1] = str2[l+1… r]luego actualice count = count + 1 . 
Imprime el conteo al final.
A continuación se muestra la implementación del enfoque: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of the
// required strings
int findAnswer(string str1, string str2, int n)
{
    int l, r;
    int ans = 2;
 
    // Searching index after longest common
    // prefix ends
    for (int i = 0; i < n; ++i) {
        if (str1[i] != str2[i]) {
            l = i;
            break;
        }
    }
 
    // Searching index before longest common
    // suffix ends
    for (int i = n - 1; i >= 0; i--) {
        if (str1[i] != str2[i]) {
            r = i;
            break;
        }
    }
 
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1);
 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else {
 
        // Checking remaining part of string
        // for equality
        for (int i = l + 1; i <= r; i++) {
            if (str1[i] != str2[i - 1]) {
                ans--;
                break;
            }
        }
 
        // Searching in right of string h
        // (g to h)
        for (int i = l + 1; i <= r; i++) {
            if (str1[i - 1] != str2[i]) {
                ans--;
                break;
            }
        }
 
        return ans;
    }
}
 
// Driver code
int main()
{
    string str1 = "toy", str2 = "try";
    int n = str1.length();
    cout << findAnswer(str1, str2, n);
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the count of the
// required strings
static int findAnswer(String str1, String str2, int n)
{
    int l = 0, r = 0;
    int ans = 2;
 
    // Searching index after longest common
    // prefix ends
    for (int i = 0; i < n; ++i)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            l = i;
            break;
        }
    }
 
    // Searching index before longest common
    // suffix ends
    for (int i = n - 1; i >= 0; i--)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            r = i;
            break;
        }
    }
 
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1);
 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else {
 
        // Checking remaining part of string
        // for equality
        for (int i = l + 1; i <= r; i++)
        {
            if (str1.charAt(i) != str2.charAt(i - 1))
            {
                ans--;
                break;
            }
        }
 
        // Searching in right of string h
        // (g to h)
        for (int i = l + 1; i <= r; i++)
        {
            if (str1.charAt(i-1) != str2.charAt(i))
            {
                ans--;
                break;
            }
        }
 
        return ans;
    }
}
 
// Driver code
public static void main(String args[])
{
    String str1 = "toy", str2 = "try";
    int n = str1.length();
    System.out.println(findAnswer(str1, str2, n));
     
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 implementation of the approach
import math as mt
 
# Function to return the count of
# the required strings
def findAnswer(str1, str2, n):
 
    l, r = 0, 0
    ans = 2
 
    # Searching index after longest
    # common prefix ends
    for i in range(n):
        if (str1[i] != str2[i]):
            l = i
            break
         
    # Searching index before longest
    # common suffix ends
    for i in range(n - 1, -1, -1):
        if (str1[i] != str2[i]):
            r = i
            break
         
    if (r < l):
        return 26 * (n + 1)
 
    # If only 1 character is different
    # in both the strings
    elif (l == r):
        return ans
    else:
 
        # Checking remaining part of
        # string for equality
        for i in range(l + 1, r + 1):
            if (str1[i] != str2[i - 1]):
                ans -= 1
                break
             
        # Searching in right of string h
        # (g to h)
        for i in range(l + 1, r + 1):
            if (str1[i - 1] != str2[i]):
                ans -= 1
                break
             
        return ans
     
# Driver code
str1 = "toy"
str2 = "try"
n = len(str1)
print(findAnswer(str1, str2, n))
 
# This code is contributed
# by Mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of the
// required strings
static int findAnswer(string str1, string str2, int n)
{
    int l = 0, r = 0;
    int ans = 2;
 
    // Searching index after longest common
    // prefix ends
    for (int i = 0; i < n; ++i)
    {
        if (str1[i] != str2[i])
        {
            l = i;
            break;
        }
    }
 
    // Searching index before longest common
    // suffix ends
    for (int i = n - 1; i >= 0; i--)
    {
        if (str1[i] != str2[i])
        {
            r = i;
            break;
        }
    }
 
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1);
 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else
    {
 
        // Checking remaining part of string
        // for equality
        for (int i = l + 1; i <= r; i++)
        {
            if (str1[i] != str2[i - 1])
            {
                ans--;
                break;
            }
        }
 
        // Searching in right of string h
        // (g to h)
        for (int i = l + 1; i <= r; i++)
        {
            if (str1[i-1] != str2[i])
            {
                ans--;
                break;
            }
        }
        return ans;
    }
}
 
// Driver code
public static void Main()
{
    String str1 = "toy", str2 = "try";
    int n = str1.Length;
    Console.WriteLine(findAnswer(str1, str2, n));
}
}
 
// This code is contributed by
// shs

<?php
// PHP implementation of the above approach
 
// Function to return the count of 
// the required strings
function findAnswer($str1, $str2, $n)
{
    $ans = 2;
 
    // Searching index after longest 
    // common prefix ends
    for ($i = 0; $i < $n; ++$i)
    {
        if ($str1[$i] != $str2[$i])
        {
            $l = $i;
            break;
        }
    }
 
    // Searching index before longest
    // common suffix ends
    for ($i = $n - 1; $i >= 0; $i--)
    {
        if ($str1[$i] != $str2[$i])
        {
            $r = $i;
            break;
        }
    }
 
    // If str1 = str2
    if ($r < $l)
        return 26 * ($n + 1);
 
    // If only 1 character is different
    // in both the strings
    else if ($l == $r)
        return $ans;
    else
    {
 
        // Checking remaining part of string
        // for equality
        for ($i = $l + 1; $i <= $r; $i++)
        {
            if ($str1[$i] != $str2[$i - 1])
            {
                $ans--;
                break;
            }
        }
 
        // Searching in right of string h
        // (g to h)
        for ($i = $l + 1; $i <= $r; $i++)
        {
            if ($str1[$i - 1] != $str2[$i])
            {
                $ans--;
                break;
            }
        }
 
        return $ans;
    }
}
 
// Driver code
$str1 = "toy";
$str2 = "try";
$n = strlen($str1);
 
echo findAnswer($str1, $str2, $n);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
    // Function to return the count of the
    // required strings
    function findAnswer( str1,  str2 , n)
    {
        var l = 0, r = 0;
        var ans = 2;
 
        // Searching index after longest common
        // prefix ends
        for (i = 0; i < n; ++i) {
            if (str1.charAt(i) != str2.charAt(i))
            {
                l = i;
                break;
            }
        }
 
        // Searching index before longest common
        // suffix ends
        for (i = n - 1; i >= 0; i--) {
            if (str1.charAt(i) != str2.charAt(i))
            {
                r = i;
                break;
            }
        }
 
        // If str1 = str2
        if (r < l)
            return 26 * (n + 1);
 
        // If only 1 character is different
        // in both the strings
        else if (l == r)
            return ans;
        else {
 
            // Checking remaining part of string
            // for equality
            for (i = l + 1; i <= r; i++) {
                if (str1.charAt(i) != str2.charAt(i - 1))
                {
                    ans--;
                    break;
                }
            }
 
            // Searching in right of string h
            // (g to h)
            for (i = l + 1; i <= r; i++) {
                if (str1.charAt(i - 1) != str2.charAt(i))
                {
                    ans--;
                    break;
                }
            }
 
            return ans;
        }
    }
 
    // Driver code
     
        var str1 = "toy", str2 = "try";
        var n = str1.length;
        document.write(findAnswer(str1, str2, n));
 
 
// This code contributed by gauravrajput1
 
</script>

2

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)