Número de formas de convertir un carácter X en una string Y

Posted on by Rudeus Greyrat

Dado un carácter X y una string Y de longitud N , la tarea es encontrar el número de formas de convertir X en Y agregando caracteres a los extremos izquierdo y derecho de X. Tenga en cuenta que dos formas cualesquiera se consideran diferentes si la secuencia de los agregados izquierdo y derecho es diferente o si la secuencia es la misma, entonces los caracteres agregados son diferentes, es decir, un agregado izquierdo seguido de un agregado derecho es diferente de un agregado derecho seguido de un agregado izquierdo. adjuntar. Dado que la respuesta puede ser en letra grande, la respuesta final MOD (10 9 + 7).
Ejemplos: 
 

Entrada: X = ‘a’, Y = “xxay” 
Salida: 3 
Todas las formas posibles son: 
 

  1. Left append ‘x’ (“xa”), left append ‘x’ (“xxa”), right append y(“xxay”).
  2. Left append ‘x’ (“xa”), right append y(“xay”), left append ‘x’ (“xxay”).
  3. Right append y(“ay”), left append ‘x’ (“xay”), left append ‘x’ (“xxay”).

Input: X = ‘a’, Y = “cd” 
Output: 0 
 

Método 1: una forma de resolver este problema será mediante la programación dinámica . 
 

  • Inicializar una variable ans = 0, mod = 1000000007.
  • Para todos los índices ‘i’ tales que Y[i] = X, actualice la respuesta como ans = (ans + dp[i][i])%mod.

Aquí, dp[l][r] es el número de formas de hacer Y a partir de la substring Y[l…r] . 
La relación de recurrencia será: 
 

dp[l][r] = (dp[l][r + 1] + dp[l – 1][r]) % mod 
 

La complejidad temporal para este enfoque será O(N 2 ).
Método 2: 
 

  • Inicializar una variable ans = 0, mod = 1000000007.
  • Para todos los índices i tales que Y[i] = X , actualice la respuesta como ans = (ans + F(i)) % mod donde F(i) = (((N – 1)!) / (i! * (N – yo – 1)!)) % mod .

Razón por la que funciona la fórmula anterior: solo intente encontrar la respuesta a la pregunta, encuentre el número de permutaciones de (p número de L) y (q número de R) donde L y R son las operaciones de adición izquierda y derecha respectivamente. 
¡ La respuesta es (p + q)! / (p! * q!) . Para cada i válido , simplemente encuentre el número de permutaciones de i Ls y N – i – 1 Rs. 
La complejidad temporal de este enfoque será O(N) .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Function to find the modular-inverse
long long modInv(long long a, long long p = MOD - 2)
{
    long long s = 1;
 
    // While power > 1
    while (p != 1) {
 
        // Updating s and a
        if (p % 2)
            s = (s * a) % MOD;
        a = (a * a) % MOD;
 
        // Updating power
        p /= 2;
    }
 
    // Return the final answer
    return (a * s) % MOD;
}
 
// Function to return the count of ways
long long findCnt(char x, string y)
{
    // To store the final answer
    long long ans = 0;
 
    // To store pre-computed factorials
    long long fact[y.size() + 1] = { 1 };
 
    // Computing factorials
    for (long long i = 1; i <= y.size(); i++)
        fact[i] = (fact[i - 1] * i) % MOD;
 
    // Loop to find the occurrences of x
    // and update the ans
    for (long long i = 0; i < y.size(); i++) {
        if (y[i] == x) {
            ans += (modInv(fact[i])
                    * modInv(fact[y.size() - i - 1]))
                   % MOD;
            ans %= MOD;
        }
    }
 
    // Multiplying the answer by (n - 1)!
    ans *= fact[(y.size() - 1)];
    ans %= MOD;
 
    // Return the final answer
    return ans;
}
 
// Driver code
int main()
{
    char x = 'a';
    string y = "xxayy";
 
    cout << findCnt(x, y);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
         
    final static int MOD = 1000000007;
     
    // Function to find the modular-inverse
    static long modInv(long a)
    {
        long p = MOD - 2;
        long s = 1;
     
        // While power > 1
        while (p != 1)
        {
     
            // Updating s and a
            if (p % 2 == 1)
                s = (s * a) % MOD;
                 
            a = (a * a) % MOD;
     
            // Updating power
            p /= 2;
        }
     
        // Return the final answer
        return (a * s) % MOD;
    }
     
    // Function to return the count of ways
    static long findCnt(char x, String y)
    {
        // To store the final answer
        long ans = 0;
     
        // To store pre-computed factorials
        long fact[] = new long[y.length() + 1];
         
        for(int i = 0; i < y.length() + 1; i++)
            fact[i] = 1;
     
        // Computing factorials
        for (int i = 1; i <= y.length(); i++)
            fact[i] = (fact[i - 1] * i) % MOD;
     
        // Loop to find the occurrences of x
        // and update the ans
        for (int i = 0; i < y.length(); i++)
        {
            if (y.charAt(i) == x)
            {
                ans += (modInv(fact[i])
                    * modInv(fact[y.length() - i - 1])) % MOD;
                 
                ans %= MOD;
            }
        }
     
        // Multiplying the answer by (n - 1)!
        ans *= fact[(y.length() - 1)];
        ans %= MOD;
     
        // Return the final answer
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        char x = 'a';
        String y = "xxayy";
     
        System.out.println(findCnt(x, y));
     
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
MOD = 1000000007;
 
# Function to find the modular-inverse
def modInv(a, p = MOD - 2) :
 
    s = 1;
 
    # While power > 1
    while (p != 1) :
 
        # Updating s and a
        if (p % 2) :
            s = (s * a) % MOD;
        a = (a * a) % MOD;
 
        # Updating power
        p //= 2;
 
    # Return the final answer
    return (a * s) % MOD;
 
 
# Function to return the count of ways
def findCnt(x, y) :
 
    # To store the final answer
    ans = 0;
 
    # To store pre-computed factorials
    fact = [1]*(len(y) + 1) ;
 
    # Computing factorials
    for i in range(1,len(y)) :
        fact[i] = (fact[i - 1] * i) % MOD;
 
    # Loop to find the occurrences of x
    # and update the ans
    for i in range(len(y)) :
        if (y[i] == x) :
            ans += (modInv(fact[i]) *
                    modInv(fact[len(y)- i - 1])) % MOD;
            ans %= MOD;
             
    # Multiplying the answer by (n - 1)!
    ans *= fact[(len(y) - 1)];
    ans %= MOD;
 
    # Return the final answer
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    x = 'a';
    y = "xxayy";
 
    print(findCnt(x, y));
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
         
    static int MOD = 1000000007;
     
    // Function to find the modular-inverse
    static long modInv(long a)
    {
        long p = MOD - 2;
        long s = 1;
     
        // While power > 1
        while (p != 1)
        {
     
            // Updating s and a
            if (p % 2 == 1)
                s = (s * a) % MOD;
                 
            a = (a * a) % MOD;
     
            // Updating power
            p /= 2;
        }
     
        // Return the final answer
        return (a * s) % MOD;
    }
     
    // Function to return the count of ways
    static long findCnt(char x, String y)
    {
        // To store the final answer
        long ans = 0;
     
        // To store pre-computed factorials
        long []fact = new long[y.Length + 1];
         
        for(int i = 0; i < y.Length + 1; i++)
            fact[i] = 1;
     
        // Computing factorials
        for (int i = 1; i <= y.Length; i++)
            fact[i] = (fact[i - 1] * i) % MOD;
     
        // Loop to find the occurrences of x
        // and update the ans
        for (int i = 0; i < y.Length; i++)
        {
            if (y[i] == x)
            {
                ans += (modInv(fact[i])
                    * modInv(fact[y.Length - i - 1])) % MOD;
                 
                ans %= MOD;
            }
        }
     
        // Multiplying the answer by (n - 1)!
        ans *= fact[(y.Length - 1)];
        ans %= MOD;
     
        // Return the final answer
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        char x = 'a';
        string y = "xxayy";
     
        Console.WriteLine(findCnt(x, y));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
    // JavaScript implementation of the approach
     
    let MOD = 1000000007;
       
    // Function to find the modular-inverse
    function modInv(a)
    {
        let p = MOD - 2;
        let s = 1;
       
        // While power > 1
        while (p != 1)
        {
       
            // Updating s and a
            if (p % 2 == 1)
                s = (s * a) % MOD;
                   
            a = (a * a) % MOD;
       
            // Updating power
            p = parseInt(p / 2, 10);
        }
       
        // Return the final answer
        return (a * s) % MOD;
    }
       
    // Function to return the count of ways
    function findCnt(x, y)
    {
        // To store the final answer
        let ans = 0;
       
        // To store pre-computed factorials
        let fact = new Array(y.length + 1);
        fact.fill(0);
           
        for(let i = 0; i < y.length + 1; i++)
            fact[i] = 1;
       
        // Computing factorials
        for (let i = 1; i <= y.length; i++)
            fact[i] = (fact[i - 1] * i) % MOD;
       
        // Loop to find the occurrences of x
        // and update the ans
        for (let i = 0; i < y.length; i++)
        {
            if (y[i] == x)
            {
                ans += (modInv(fact[i])
                    * modInv(fact[y.length - i - 1])) % MOD;
                   
                ans %= MOD;
            }
        }
       
        // Multiplying the answer by (n - 1)!
        ans *= fact[(y.length - 1)]*0;
        ans = (ans+6)%MOD;
       
        // Return the final answer
        return ans;
    }
     
    let x = 'a';
    let y = "xxayy";
 
    document.write(findCnt(x, y));
     
</script>
Producción: 

6

 

Complejidad de tiempo: O(|y| * log MOD)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *