Conteo de strings posible reemplazando dos mismos caracteres consecutivos con un nuevo carácter

Posted on by Rudeus Greyrat

String dada str . La tarea es contar el número de todas las strings diferentes posibles si dos mismos caracteres consecutivos de la string pueden ser reemplazados por un carácter diferente.
Ejemplos 
 

Entrada: str = «abclll» 
Salida: 3 
Explicación: 
Puede haber 3 strings diferentes, incluida la string original, como se muestra en la siguiente figura: – 
 

Entrada: str = «abcllldefkkkk» 
Salida: 15 
Explicación: 
Puede haber 15 strings diferentes, incluida la string original, como se muestra en la siguiente figura: – 
 

 

Enfoque: 
Se observaron las siguientes propiedades para reemplazar dos caracteres iguales a la vez: 
 

  • Si para string = «aaa » de longitud 3 reemplazamos dos «aa» con un carácter, digamos «K» , entonces el número total de diferentes strings posibles, incluida la string original, es: – Ka, aK, aaa . Por lo tanto, el número de strings diferentes sigue la propiedad de Número de Fibonacci de la longitud de los caracteres consecutivos en la string.
  • Si for string = “ aaadefyyyy ”, entonces el número total de posibles strings diferentes se iguala al producto de las combinaciones de strings “aaa” y “yyyy” reemplazando los dos caracteres consecutivos a la vez.

Por lo tanto, a partir de las dos observaciones anteriores, el recuento de diferentes strings posibles con N caracteres consecutivos viene dado por el N-ésimo número de Fibonacci . Por lo tanto, el número total de diferentes strings posibles para la string dada str es igual al producto del conteo de diferentes strings posibles para cada substring con el mismo carácter.
Los siguientes son los pasos: 
 

  1. Cuente ( digamos cnt ) el número de caracteres consecutivos que son iguales en la string dada str .
  2. Para contar las diferentes strings posibles para la cuenta cnt , busque el valor de la Secuencia de Fibonacci en cnt .
  3. Repita los pasos anteriores para todos los caracteres consecutivos en la string dada str .
  4. El recuento total de diferentes strings posibles se iguala al producto de todo el valor de la Secuencia de Fibonacci obtenido por cada recuento de caracteres consecutivos.

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

C++

// C++ program to count the
// different possible string
// form by replacing two same
// characters with one
#include <bits/stdc++.h>
using namespace std;
 
// Array to find the fibonacci
// sequence
int fib[100005];
 
// Function to find the
// fibonacci sequence
void computeFibonacci()
{
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < 100005; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
 
// Function to count all
// possible strings
int countString(string str)
{
 
    // Initialize ans = 1
    int ans = 1;
    int cnt = 1;
 
    for (int i = 1; str[i]; i++) {
 
        // If two consecutive
        // char are same
        // increase cnt
        if (str[i] == str[i - 1]) {
            cnt++;
        }
 
        // Else multiply the
        // fib[cnt] to ans
        // and initialize ans
        // to 1
        else {
            ans = ans * fib[cnt];
            cnt = 1;
        }
    }
    //
    // If str = abcdeeee, then
    // for last "eeee" the
    // count munst be updated
    ans = ans * fib[cnt];
 
    // Return the total count
    return ans;
}
 
// Driver's Code
int main()
{
    string str = "abdllldefkkkk";
 
    // Function to precompute
    // all the fibonacci number
    computeFibonacci();
 
    // Function call to find
    // the count
    cout << countString(str);
    return 0;
}

Java

// Java program to count the
// different possible string
// form by replacing two same
// characters with one
class GFG {
     
    // Array to find the fibonacci
    // sequence
    static int fib[] = new int[100005];
     
    // Function to find the
    // fibonacci sequence
    static void computeFibonacci()
    {
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < 100005; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
     
    // Function to count all
    // possible strings
    static int countString(String str)
    {
     
        // Initialize ans = 1
        int ans = 1;
        int cnt = 1;
     
        for (int i = 1; i<str.length(); i++) {
     
            // If two consecutive
            // char are same
            // increase cnt
            if (str.charAt(i) == str.charAt(i - 1)) {
                cnt++;
            }
     
            // Else multiply the
            // fib[cnt] to ans
            // and initialize ans
            // to 1
            else {
                ans = ans * fib[cnt];
                cnt = 1;
            }
        }
          
        // If str = abcdeeee, then
        // for last "eeee" the
        // count munst be updated
        ans = ans * fib[cnt];
     
        // Return the total count
        return ans;
    }
     
    // Driver's Code
    public static void main (String[] args)
    {
        String str = "abdllldefkkkk";
     
        // Function to precompute
        // all the fibonacci number
        computeFibonacci();
     
        // Function call to find
        // the count
        System.out.println(countString(str));
    }
}
 
// This code is contributed by Yash_R

Python3

# Python3 program to count the
# different possible string
# form by replacing two same
# characters with one
 
# Array to find the fibonacci
# sequence
fib = [0]*100005;
 
# Function to find the
# fibonacci sequence
def computeFibonacci() :
 
    fib[0] = 1;
    fib[1] = 1;
    for i in range(2, 100005) :
        fib[i] = fib[i - 1] + fib[i - 2];
 
# Function to count all
# possible strings
def countString(string) :
 
    # Initialize ans = 1
    ans = 1;
    cnt = 1;
 
    for i in range(1, len(string)) :
 
        # If two consecutive
        # char are same
        # increase cnt
        if (string[i] == string[i - 1]) :
            cnt += 1;
 
        # Else multiply the
        # fib[cnt] to ans
        # and initialize ans
        # to 1
        else :
            ans = ans * fib[cnt];
            cnt = 1;
             
    # If str = abcdeeee, then
    # for last "eeee" the
    # count munst be updated
    ans = ans * fib[cnt];
 
    # Return the total count
    return ans;
 
# Driver's Code
if __name__ == "__main__" :
 
    string = "abdllldefkkkk";
 
    # Function to precompute
    # all the fibonacci number
    computeFibonacci();
 
    # Function call to find
    # the count
    print(countString(string));
     
# This code is contributed by Yash_R

C#

// C# program to count the
// different possible string
// form by replacing two same
// characters with one
using System;
 
class GFG {
     
    // Array to find the fibonacci
    // sequence
    static int []fib = new int[100005];
     
    // Function to find the
    // fibonacci sequence
    static void computeFibonacci()
    {
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < 100005; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
     
    // Function to count all
    // possible strings
    static int countString(string str)
    {
     
        // Initialize ans = 1
        int ans = 1;
        int cnt = 1;
     
        for (int i = 1; i < str.Length; i++) {
     
            // If two consecutive
            // char are same
            // increase cnt
            if (str[i] == str[i - 1]) {
                cnt++;
            }
     
            // Else multiply the
            // fib[cnt] to ans
            // and initialize ans
            // to 1
            else {
                ans = ans * fib[cnt];
                cnt = 1;
            }
        }
          
        // If str = abcdeeee, then
        // for last "eeee" the
        // count munst be updated
        ans = ans * fib[cnt];
     
        // Return the total count
        return ans;
    }
     
    // Driver's Code
    public static void Main (string[] args)
    {
        string str = "abdllldefkkkk";
     
        // Function to precompute
        // all the fibonacci number
        computeFibonacci();
     
        // Function call to find
        // the count
        Console.WriteLine(countString(str));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript program to count the
// different possible string
// form by replacing two same
// characters with one    
 
// Array to find the fibonacci
// sequence
     fib = Array(100005).fill(0);
 
    // Function to find the
    // fibonacci sequence
    function computeFibonacci()
    {
        fib[0] = 1;
        fib[1] = 1;
        for (i = 2; i < 100005; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
 
    // Function to count all
    // possible strings
    function countString( str) {
 
        // Initialize ans = 1
        var ans = 1;
        var cnt = 1;
 
        for (i = 1; i < str.length; i++)
        {
 
            // If two consecutive
            // char are same
            // increase cnt
            if (str.charAt(i) == str.charAt(i - 1))
            {
                cnt++;
            }
 
            // Else multiply the
            // fib[cnt] to ans
            // and initialize ans
            // to 1
            else {
                ans = ans * fib[cnt];
                cnt = 1;
            }
        }
 
        // If str = abcdeeee, then
        // for last "eeee" the
        // count munst be updated
        ans = ans * fib[cnt];
 
        // Return the total count
        return ans;
    }
 
    // Driver's Code
     
        var str = "abdllldefkkkk";
 
        // Function to precompute
        // all the fibonacci number
        computeFibonacci();
 
        // Function call to find
        // the count
        document.write(countString(str));
 
// This code contributed by umadevi9616
 
</script>
Producción: 

15

 

Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
 

Publicación traducida automáticamente

Artículo escrito por TanujYadav 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 *