Cuente secuencias distintas obtenidas al reemplazar todos los elementos de subarreglos que tienen el primer y el último elementos iguales con el primer elemento cualquier número de veces

Dada una array arr[] que consta de N enteros, la tarea es encontrar la cantidad de secuencias diferentes que se pueden formar después de realizar la siguiente operación en la array dada arr[] cualquier cantidad de veces.

Elija dos índices i y j tales que arr[i] sea igual a arr[j] y actualice todos los elementos en el rango [i, j] en la array a arr[i] .

Ejemplos:

Entrada: arr[] = {1, 2, 1, 2, 2}
Salida: 3
Explicación:
Puede haber tres secuencias posibles:

1. La array inicial {1, 2, 1, 2, 2}.
2. Elija los índices 0 y 2 y como arr[0](= 1) y arr[2](= 1) son iguales y actualice los elementos de la array arr[] sobre el rango [0, 2] a arr[0](= 1 ). La nueva secuencia obtenida es {1, 1, 1, 2, 2}.
3. Elija los índices 1 y 3 y como arr[1](= 2) y arr[3](= 2) son iguales y actualice los elementos de la array arr[] sobre el rango [1, 3] a arr[1](= 2 ). La nueva secuencia obtenida es {1, 2, 2, 2, 2}.

Por lo tanto, el número total de secuencias formadas es 3.

Entrada: arr[] = {4, 2, 5, 4, 2, 4}
Salida: 5

Enfoque: Este problema se puede resolver usando Programación Dinámica . Siga los pasos a continuación para resolver el problema:

• Inicialice una array auxiliar dp[] donde dp[i] almacena la cantidad de secuencias diferentes que son posibles por los primeros i elementos de la array dada arr[] e inicialice dp[0] como 1 .
• Inicialice una array lastOccur[] donde lastOccur[i] almacena la última aparición del elemento arr[i] en los primeros i elementos de la array arr[] e inicialice lastOccur[0] con -1 .
• Iterar sobre el rango [1, N] usando la variable i y realizar los siguientes pasos:
  • Actualice el valor de dp[i] como dp[i – 1] .
  • Si la última aparición del elemento actual no es igual a -1 y menor que (i – 1) , agregue el valor de dp[lastOccur[curEle]] a dp[i] .
  • Actualice el valor de lastOccur[curEle] como i .
• Después de completar los pasos anteriores, imprima el valor de dp[N] como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of sequences
// satisfying the given criteria
void countPossiblities(int arr[], int n)
{
    // Stores the index of the last
    // occurrence of the element
    int lastOccur[100000];
    for (int i = 0; i < n; i++) {
        lastOccur[i] = -1;
    }
 
    // Initialize an array to store the
    // number of different sequences
    // that are possible of length i
    int dp[n + 1];
 
    // Base Case
    dp[0] = 1;
 
    for (int i = 1; i <= n; i++) {
 
        int curEle = arr[i - 1];
 
        // If no operation is applied
        // on ith element
        dp[i] = dp[i - 1];
 
        // If operation is applied on
        // ith element
        if (lastOccur[curEle] != -1
            & lastOccur[curEle] < i - 1) {
            dp[i] += dp[lastOccur[curEle]];
        }
 
        // Update the last occurrence
        // of curEle
        lastOccur[curEle] = i;
    }
 
    // Finally, print the answer
    cout << dp[n] << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 1, 2, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    countPossiblities(arr, N);
 
    return 0;
}

// Java Program for the above approach
import java.io.*;
 
class GFG {
 
    // Function to count number of sequences
    // satisfying the given criteria
    static void countPossiblities(int arr[], int n)
    {
        // Stores the index of the last
        // occurrence of the element
        int[] lastOccur = new int[100000];
        for (int i = 0; i < n; i++) {
            lastOccur[i] = -1;
        }
 
        // Initialize an array to store the
        // number of different sequences
        // that are possible of length i
        int[] dp = new int[n + 1];
 
        // Base Case
        dp[0] = 1;
 
        for (int i = 1; i <= n; i++) {
 
            int curEle = arr[i - 1];
 
            // If no operation is applied
            // on ith element
            dp[i] = dp[i - 1];
 
            // If operation is applied on
            // ith element
            if (lastOccur[curEle] != -1
                & lastOccur[curEle] < i - 1) {
                dp[i] += dp[lastOccur[curEle]];
            }
 
            // Update the last occurrence
            // of curEle
            lastOccur[curEle] = i;
        }
 
        // Finally, print the answer
        System.out.println(dp[n]);
    }
 
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 1, 2, 2 };
        int N = arr.length;
        countPossiblities(arr, N);
 
    }
}
 
    // This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to count number of sequences
# satisfying the given criteria
def countPossiblities(arr, n):
     
    # Stores the index of the last
    # occurrence of the element
    lastOccur = [-1] * 100000
 
    # Initialize an array to store the
    # number of different sequences
    # that are possible of length i
    dp = [0] * (n + 1)
 
    # Base Case
    dp[0] = 1
 
    for i in range(1, n + 1):
        curEle = arr[i - 1]
 
        # If no operation is applied
        # on ith element
        dp[i] = dp[i - 1]
 
        # If operation is applied on
        # ith element
        if (lastOccur[curEle] != -1 and
            lastOccur[curEle] < i - 1):
            dp[i] += dp[lastOccur[curEle]]
 
        # Update the last occurrence
        # of curEle
        lastOccur[curEle] = i
 
    # Finally, print the answer
    print(dp[n])
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 1, 2, 2 ]
    N = len(arr)
     
    countPossiblities(arr, N)
 
# This code is contributed by mohit kumar 29

// C# Program for the above approach
using System;
 
class GFG {
 
    // Function to count number of sequences
    // satisfying the given criteria
    static void countPossiblities(int[] arr, int n)
    {
        // Stores the index of the last
        // occurrence of the element
        int[] lastOccur = new int[100000];
        for (int i = 0; i < n; i++) {
            lastOccur[i] = -1;
        }
 
        // Initialize an array to store the
        // number of different sequences
        // that are possible of length i
        int[] dp = new int[n + 1];
 
        // Base Case
        dp[0] = 1;
 
        for (int i = 1; i <= n; i++) {
 
            int curEle = arr[i - 1];
 
            // If no operation is applied
            // on ith element
            dp[i] = dp[i - 1];
 
            // If operation is applied on
            // ith element
            if (lastOccur[curEle] != -1
                & lastOccur[curEle] < i - 1) {
                dp[i] += dp[lastOccur[curEle]];
            }
 
            // Update the last occurrence
            // of curEle
            lastOccur[curEle] = i;
        }
 
        // Finally, print the answer
        Console.WriteLine(dp[n]);
    }
 
    public static void Main()
    {
        int[] arr = { 1, 2, 1, 2, 2 };
        int N = arr.Length;
        countPossiblities(arr, N);
    }
}
 
// This code is contributed by subham348.

<script>
       // JavaScript Program for the above approach
 
       // Function to count number of sequences
       // satisfying the given criteria
       function countPossiblities(arr, n)
       {
        
           // Stores the index of the last
           // occurrence of the element
           let lastOccur = new Array(100000);
           for (let i = 0; i < n; i++) {
               lastOccur[i] = -1;
           }
 
           // Initialize an array to store the
           // number of different sequences
           // that are possible of length i
           dp = new Array(n + 1);
 
           // Base Case
           dp[0] = 1;
 
           for (let i = 1; i <= n; i++) {
 
               let curEle = arr[i - 1];
 
               // If no operation is applied
               // on ith element
               dp[i] = dp[i - 1];
 
               // If operation is applied on
               // ith element
               if (lastOccur[curEle] != -1
                   & lastOccur[curEle] < i - 1) {
                   dp[i] += dp[lastOccur[curEle]];
               }
 
               // Update the last occurrence
               // of curEle
               lastOccur[curEle] = i;
           }
 
           // Finally, print the answer
           document.write(dp[n] + "<br>");
       }
 
       // Driver Code
 
       let arr = [1, 2, 1, 2, 2];
       let N = arr.length;
       countPossiblities(arr, N);
 
 
   // This code is contributed by Potta Lokesh
 
   </script>

Producción:

3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)