Número mínimo de dígitos que se eliminarán para que todos los dígitos o los dígitos alternos sean iguales

Dada una string numérica str , la tarea es encontrar el número mínimo de dígitos que se eliminarán de la string de modo que satisfaga cualquiera de las siguientes condiciones: 
 

• Todos los elementos de la string son iguales.
• Todos los elementos en la posición par son iguales y todos los elementos en la posición impar son iguales, lo que significa que la string se alterna con la misma ocurrencia de cada dígito.

Ejemplos:

Entrada: s = “95831” 
Salida: 3 
Explicación: 
En este ejemplo, elimine tres elementos cualquiera de la string para que sea alterna, es decir, “95” tiene 9 en el índice par y 5 en el índice impar y, por lo tanto, satisface la segunda condición. 
Entrada: s = “100120013” 
Salida: 5 
Explicación: 
En este caso, haga la string 0000 o haga la string 1010. En ambos casos, el elemento mínimo que debe eliminarse de la string será 5 . 
 

Enfoque: La idea es usar el Enfoque Codicioso . A continuación se muestran los pasos: 
 

1. Dado que todos los caracteres en la string resultante se alternan y son iguales, la substring más pequeña de dígitos distintos tendrá una longitud de 2.
2. Como, solo hay 10 tipos diferentes de dígitos que van del 0 al 9 . La idea es iterar todas las strings posibles de longitud 2 y encontrar la ocurrencia de la subsecuencia formada por ellas.
3. Por lo tanto, encuentre todas las combinaciones posibles del primer y segundo carácter de la string de dos dígitos anterior y construya con avidez la subsecuencia más larga posible de s que comience con esos caracteres.
4. La diferencia entre la longitud de la string y la longitud máxima de la subsecuencia con dígitos alternos en el paso anterior es el resultado requerido.

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 find longest possible
// subsequence of s beginning with x and y
int solve(string s, int x, int y)
{
    int res = 0;
 
    // Iterate over the string
    for (auto c : s) {
        if (c - '0' == x) {
 
            // Increment count
            res++;
 
            // Swap the positions
            swap(x, y);
        }
    }
 
    if (x != y && res % 2 == 1)
        --res;
 
    // Return the result
    return res;
}
 
// Function that finds all the
// possible pairs
int find_min(string s)
{
    int count = 0;
    for (int i = 0; i < 10; i++) {
 
        for (int j = 0; j < 10; j++) {
 
            // Update count
            count = max(count,
                        solve(s, i, j));
        }
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
int main()
{
    // Given string s
    string s = "100120013";
 
    // Find the size of the string
    int n = s.size();
 
    // Function Call
    int answer = find_min(s);
 
    // This value is the count of
    // minimum element to be removed
    cout << (n - answer);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find longest possible
// subsequence of s beginning with x and y
static int solve(String s, int x, int y)
{
    int res = 0;
 
    // Iterate over the String
    for (char c : s.toCharArray())
    {
        if (c - '0' == x)
        {
 
            // Increment count
            res++;
 
            // Swap the positions
            x = x+y;
            y = x-y;
            x = x-y;
        }
    }
 
    if (x != y && res % 2 == 1)
        --res;
 
    // Return the result
    return res;
}
 
// Function that finds all the
// possible pairs
static int find_min(String s)
{
    int count = 0;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
 
            // Update count
            count = Math.max(count,
                             solve(s, i, j));
        }
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given String s
    String s = "100120013";
 
    // Find the size of the String
    int n = s.length();
 
    // Function Call
    int answer = find_min(s);
 
    // This value is the count of
    // minimum element to be removed
    System.out.print((n - answer));
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
 
# Function to find longest possible
# subsequence of s beginning with x and y
def solve(s, x, y):
 
    res = 0
 
    # Iterate over the string
    for c in s:
        if(ord(c) - ord('0') == x):
 
            # Increment count
            res += 1
 
            # Swap the positions
            x, y = y, x
 
    if(x != y and res % 2 == 1):
        res -= 1
 
    # Return the result
    return res
 
# Function that finds all the
# possible pairs
def find_min(s):
 
    count = 0
    for i in range(10):
        for j in range(10):
 
            # Update count
            count = max(count, solve(s, i, j))
 
    # Return the answer
    return count
 
# Driver Code
 
# Given string s
s = "100120013"
 
# Find the size of the string
n = len(s)
 
# Function call
answer = find_min(s)
 
# This value is the count of
# minimum element to be removed
print(n - answer)
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
class GFG{
 
// Function to find longest possible
// subsequence of s beginning with x and y
static int solve(String s, int x, int y)
{
    int res = 0;
 
    // Iterate over the String
    foreach (char c in s.ToCharArray())
    {
        if (c - '0' == x)
        {
 
            // Increment count
            res++;
 
            // Swap the positions
            x = x + y;
            y = x - y;
            x = x - y;
        }
    }
 
    if (x != y && res % 2 == 1)
        --res;
 
    // Return the result
    return res;
}
 
// Function that finds all the
// possible pairs
static int find_min(String s)
{
    int count = 0;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
 
            // Update count
            count = Math.Max(count,
                             solve(s, i, j));
        }
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given String s
    String s = "100120013";
 
    // Find the size of the String
    int n = s.Length;
 
    // Function Call
    int answer = find_min(s);
 
    // This value is the count of
    // minimum element to be removed
    Console.Write((n - answer));
}
}
 
// This code is contributed by gauravrajput1

<script>
// JavaScript program for the above approach
 
 
// Function to find longest possible
// subsequence of s beginning with x and y
function solve(s, x, y)
{
    let res = 0;
 
    // Iterate over the string
    for (let c of s) {
        if (c - '0' == x) {
 
            // Increment count
            res++;
 
            // Swap the positions
            x = x+y;
            y = x-y;
            x = x-y;
        }
    }
 
    if (x != y && res % 2 == 1)
        --res;
 
    // Return the result
    return res;
}
 
// Function that finds all the
// possible pairs
function find_min(s)
{
    let count = 0;
    for (let i = 0; i < 10; i++) {
 
        for (let j = 0; j < 10; j++) {
 
            // Update count
            count = Math.max(count,
                        solve(s, i, j));
        }
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
    // Given string s
    let s = "100120013";
 
    // Find the size of the string
    let n = s.length;
 
    // Function Call
    let answer = find_min(s);
 
    // This value is the count of
    // minimum element to be removed
    document.write(n - answer);
 
 
 
 
// This code is contributed by Surbhi Tyagi.
</script>

5

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