Minimice la longitud de una array eliminando subarreglos similares de ambos extremos

Dada una array arr[] de tamaño N , la tarea es minimizar la longitud de la array dada eliminando repetidamente subarreglos desde el principio y el final de la array que consiste en el mismo elemento único.

Ejemplos:

Entrada: arr[] = { 3, 1, 2, 1, 1, 2, 1, 3 }
Salida: 0
Explicación:

1. Dado que tanto el primer como el último elemento son 3, eliminarlos modifica arr[] a {1, 2, 1, 1, 2, 1}.
2. Dado que tanto el primer como el último elemento son 1, eliminarlos modifica arr[] a {2, 1, 1, 2}.
3. Dado que tanto el primer como el último elemento son 2, eliminarlos modifica arr[] a {1, 1}.
4. Dado que tanto el primer como el último elemento son 1, eliminarlos modifica arr[] a {}.

Entrada: arr[] = {1, 1, 2, 3, 3, 1, 2, 2, 1}
Salida: 3
Explicación:

1. Al quitar { 1, 1 } del principio y { 1 } del final, se modifica arr[] a { 2, 3, 3, 1, 2, 2 }.
2. Quitar { 2 } del principio y { 2, 2 } del final modifica arr[] a { 3, 3, 1 }.
3. No se pueden eliminar más elementos.

Enfoque: La idea es utilizar la técnica de dos puntos para resolver el problema. Siga los pasos a continuación para resolver el problema:

1. Inicialice dos punteros front = 0 , back = N – 1 para atravesar la array desde ambos extremos simultáneamente.
2. Atraviese la array arr[] hasta el frente <atrás:
   • Si ambos elementos son diferentes, rompa el bucle.
   • De lo contrario, incremente el puntero frontal y disminuya el puntero posterior hasta que apunten a un elemento diferente al actual.
3. Imprime la diferencia entre la posición de dos punteros como la longitud minimizada de la array.

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 minimize length of
// the array by removing similar
// subarrays from both ends of the array
void findMinLength(int arr[], int N)
{
    // Initialize two pointers
    int front = 0, back = N - 1;
 
    while (front < back) {
 
        // Stores the current integer
        int x = arr[front];
 
        // Check if the elements at
        // both ends are same or not
        if (arr[front] != arr[back])
            break;
 
        // Move the front pointer
        while (arr[front] == x
               && front <= back)
            front++;
 
        // Move the rear pointer
        while (arr[back] == x
               && front <= back)
            back--;
    }
 
    // Print the minimized length of the array
    cout << back - front + 1 << endl;
}
 
// Driver Code
int main()
{
    // Input
    int arr[] = { 1, 1, 2, 3, 3, 1, 2, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to find the
    // minimized length of the array
    findMinLength(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to minimize length of
  // the array by removing similar
  // subarrays from both ends of the array
  static void findMinLength(int arr[], int N)
  {
    // Initialize two pointers
    int front = 0, back = N - 1;
    while (front < back) {
 
      // Stores the current integer
      int x = arr[front];
 
      // Check if the elements at
      // both ends are same or not
      if (arr[front] != arr[back])
        break;
 
      // Move the front pointer
      while (arr[front] == x
             && front <= back)
        front++;
 
      // Move the rear pointer
      while (arr[back] == x
             && front <= back)
        back--;
    }
 
    // Print the minimized length of the array
    System.out.println( back - front + 1 );
  }
 
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Input
    int arr[] = { 1, 1, 2, 3, 3, 1, 2, 2, 1 };
    int N = arr.length;
 
    // Function call to find the
    // minimized length of the array
    findMinLength(arr, N);
  }
}
 
// This code is contributed by sanjoy_62.

# Python program for
# the above approach
 
# Function to minimize length of
# the array by removing similar
# subarrays from both ends of the array
def findMinLength(arr, N):
   
    # Initialize two pointers
    front = 0
    back = N - 1
    while (front < back):
       
        # Stores the current integer
        x = arr[front]
         
        # Check if the elements at
        # both ends are same or not
        if arr[front] != arr[back]:
            break
             
            # Move the front pointer
        while (arr[front] == x and front <= back):
            front += 1
             
            # Move the rear pointer
        while (arr[back] == x and front <= back):
            back -= 1
 
    # Print the minimized length of the array
    print(back - front + 1)
 
# Driver Code
# Input
arr = [1, 1, 2, 3, 3, 1, 2, 2, 1]
N = len(arr)
 
# Function call to find the
# minimized length of the array
findMinLength(arr, N)
 
# This code is contributed by sudhanshugupta2019a.

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to minimize length of
  // the array by removing similar
  // subarrays from both ends of the array
  static void findMinLength(int []arr, int N)
  {
 
    // Initialize two pointers
    int front = 0, back = N - 1;
    while (front < back)
    {
 
      // Stores the current integer
      int x = arr[front];
 
      // Check if the elements at
      // both ends are same or not
      if (arr[front] != arr[back])
        break;
 
      // Move the front pointer
      while (arr[front] == x
             && front <= back)
        front++;
 
      // Move the rear pointer
      while (arr[back] == x
             && front <= back)
        back--;
    }
 
    // Print the minimized length of the array
    Console.WriteLine( back - front + 1 );
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Input
    int []arr = { 1, 1, 2, 3, 3, 1, 2, 2, 1 };
    int N = arr.Length;
 
    // Function call to find the
    // minimized length of the array
    findMinLength(arr, N);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
// JavaScript program for
// the above approach
 
// Function to minimize length of
// the array by removing similar
// subarrays from both ends of the array
function findMinLength(arr, N)
{
 
    // Initialize two pointers
    let front = 0, back = N - 1;
    while (front < back)
    {
 
        // Stores the current integer
        let x = arr[front];
 
        // Check if the elements at
        // both ends are same or not
        if (arr[front] != arr[back])
            break;
 
        // Move the front pointer
        while (arr[front] == x
            && front <= back)
            front++;
 
        // Move the rear pointer
        while (arr[back] == x
            && front <= back)
            back--;
    }
 
    // Print the minimized length of the array
    document.write(back - front + 1);
    document.write("<br>");
}
 
// Driver Code
 
    // Input
    let arr = [ 1, 1, 2, 3, 3, 1, 2, 2, 1 ];
    let N = arr.length;
 
    // Function call to find the
    // minimized length of the array
    findMinLength(arr, N);
 
// This code is contributed by Surbhi Tyagi.
</script>

3

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