Eliminaciones mínimas requeridas de modo que la string dada consista solo en un par de caracteres alternos

Dada una string S , la tarea es encontrar la eliminación mínima de caracteres necesaria para que la string S consista solo en dos caracteres alternos.

Ejemplos:

Entrada: S = “ adebbeeaebd”
Salida: 7
Explicación: Eliminar todas las apariciones de ‘b’ y ‘e’ modifica la string a “adad”, que consiste en apariciones alternas de ‘a’ y ‘d’.

Entrada: S = “ abccd”
Salida: 3
Explicación: Eliminar todas las apariciones de ‘c’ y ‘d’ modifica la string a «ab», que consiste en alternar ‘a’ y ‘b’.

 

Enfoque: el problema se puede resolver generando todos los 26 2 pares posibles de letras inglesas y encontrar el par con una longitud máxima de ocurrencias alternas, digamos len , en la string S . Luego, imprima la cantidad de caracteres necesarios para eliminarlos restando len de N .

Siga los pasos a continuación para resolver el problema dado:

  1. Inicialice una variable, digamos len, para almacenar la longitud máxima de ocurrencias alternas de un par de caracteres.
  2. Repita cada posible par de alfabetos ingleses y para cada par, realice las siguientes operaciones:
    • Itere sobre los caracteres de la string S y encuentre la longitud, digamos newlen , de ocurrencias alternas de dos caracteres de la string S .
    • Compruebe si len es más pequeño que newlen o no. Si se determina que es cierto, actualice len = newlen .
  3. Finalmente, imprima N – len como la respuesta requerida.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// length of alternating occurrences
// of a pair of characters in a string s
int findLength(string s, char i, char j)
{
    // Stores the next character
    // for alternating sequence
    char required = i;
 
    // Stores the length of alternating
    // occurrences of a pair of characters
    int length = 0;
 
    // Traverse the given string
    for (char curr : s) {
 
        // If current character is same
        // as the required character
        if (curr == required) {
 
            // Increase length by 1
            length += 1;
 
            // Reset required character
            if (required == i)
                required = j;
            else
                required = i;
        }
    }
 
    // Return the length
    return length;
}
 
// Function to find minimum characters
// required to be deleted from S to
// obtain an alternating sequence
int minimumDeletions(string S)
{
 
    // Stores maximum length
    // of alternating sequence
    // of two characters
    int len = 0;
 
    // Stores length of the string
    int n = S.length();
 
    // Generate every pair
    // of English alphabets
    for (char i = 'a'; i <= 'z'; i++) {
        for (char j = i + 1; j <= 'z'; j++) {
 
            // Function call to find length
            // of alternating sequence for
            // current pair of characters
            int newLen = findLength(S, i, j);
 
            // Update len to store the maximum
            // of len and newLen in len
            len = max(len, newLen);
        }
    }
 
    // Return n - len as the final result
    return n - len;
}
 
// Driver Code
int main()
{
    // Given Input
    string S = "adebbeeaebd";
 
    // Function call to find minimum
    // characters required to be removed
    // from S to make it an alternating
    // sequence of a pair of characters
    cout << minimumDeletions(S);
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function to find the maximum
// length of alternating occurrences
// of a pair of characters in a string s
static int findLength(String s, char i, char j)
{
     
    // Stores the next character
    // for alternating sequence
    char required = i;
 
    // Stores the length of alternating
    // occurrences of a pair of characters
    int length = 0;
 
    // Traverse the given string
    for(int k = 0; k < s.length(); k++)
    {
        char curr = s.charAt(k);
         
        // If current character is same
        // as the required character
        if (curr == required)
        {
             
            // Increase length by 1
            length += 1;
 
            // Reset required character
            if (required == i)
                required = j;
            else
                required = i;
        }
    }
 
    // Return the length
    return length;
}
 
// Function to find minimum characters
// required to be deleted from S to
// obtain an alternating sequence
static int minimumDeletions(String S)
{
     
    // Stores maximum length
    // of alternating sequence
    // of two characters
    int len = 0;
 
    // Stores length of the string
    int n = S.length();
 
    // Generate every pair
    // of English alphabets
    for(int i = 0; i < 26; i++)
    {
        for(int j = i + 1; j < 26; j++)
        {
             
            // Function call to find length
            // of alternating sequence for
            // current pair of characters
            int newLen = findLength(S, (char)(i + 97),
                                       (char)(j + 97));
 
            // Update len to store the maximum
            // of len and newLen in len
            len = Math.max(len, newLen);
        }
    }
 
    // Return n - len as the final result
    return n - len;
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given Input
    String S = "adebbeeaebd";
 
    // Function call to find minimum
    // characters required to be removed
    // from S to make it an alternating
    // sequence of a pair of characters
    System.out.print(minimumDeletions(S));
}
}
 
// This code is contributed by AnkThon

Python3

# Python3 program for the above approach
 
# Function to find the maximum
# length of alternating occurrences
# of a pair of characters in a string s
def findLength(s, i, j):
     
    # Stores the next character
    # for alternating sequence
    required = i
 
    # Stores the length of alternating
    # occurrences of a pair of characters
    length = 0
 
    # Traverse the given string
    for curr in s:
         
        # If current character is same
        # as the required character
        if (curr == required):
             
            # Increase length by 1
            length += 1
 
            # Reset required character
            if (required == i):
                required = j
            else:
                required = i
 
    # Return the length
    return length
 
# Function to find minimum characters
# required to be deleted from S to
# obtain an alternating sequence
def minimumDeletions(S):
     
    # Stores maximum length
    # of alternating sequence
    # of two characters
    len1 = 0
 
    # Stores length of the string
    n = len(S)
 
    # Generate every pair
    # of English alphabets
    for i in range(0, 26, 1):
        for j in range(i + 1, 26, 1):
             
            # Function call to find length
            # of alternating sequence for
            # current pair of characters
            newLen = findLength(S, chr(i + 97),
                                   chr(j + 97))
 
            # Update len to store the maximum
            # of len and newLen in len
            len1 = max(len1, newLen)
 
    # Return n - len as the final result
    return n - len1
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    S = "adebbeeaebd"
 
    # Function call to find minimum
    # characters required to be removed
    # from S to make it an alternating
    # sequence of a pair of characters
    print(minimumDeletions(S))
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the maximum
// length of alternating occurrences
// of a pair of characters in a string s
static int findLength(string s, char i, char j)
{
     
    // Stores the next character
    // for alternating sequence
    char required = i;
 
    // Stores the length of alternating
    // occurrences of a pair of characters
    int length = 0;
 
    // Traverse the given string
    for(int k = 0; k < s.Length; k++)
    {
        char curr = s[k];
         
        // If current character is same
        // as the required character
        if (curr == required)
        {
             
            // Increase length by 1
            length += 1;
 
            // Reset required character
            if (required == i)
                required = j;
            else
                required = i;
        }
    }
 
    // Return the length
    return length;
}
 
// Function to find minimum characters
// required to be deleted from S to
// obtain an alternating sequence
static int minimumDeletions(string S)
{
     
    // Stores maximum length
    // of alternating sequence
    // of two characters
    int len = 0;
 
    // Stores length of the string
    int n = S.Length;
 
    // Generate every pair
    // of English alphabets
    for(int i = 0; i < 26; i++)
    {
        for(int j = i + 1; j < 26; j++)
        {
             
            // Function call to find length
            // of alternating sequence for
            // current pair of characters
            int newLen = findLength(S, (char)(i + 97),
                                       (char)(j + 97));
 
            // Update len to store the maximum
            // of len and newLen in len
            len = Math.Max(len, newLen);
        }
    }
 
    // Return n - len as the final result
    return n - len;
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given Input
    string S = "adebbeeaebd";
 
    // Function call to find minimum
    // characters required to be removed
    // from S to make it an alternating
    // sequence of a pair of characters
    Console.WriteLine(minimumDeletions(S));
}
}
 
// This code is contributed by avijitmondal1998

Javascript

<script>
 
// JavaScript program for the above approach
 
     
// Function to find the maximum
// length of alternating occurrences
// of a pair of characters in a string s
function findLength( s,  i,  j)
{
     
    // Stores the next character
    // for alternating sequence
    var required = i;
 
    // Stores the length of alternating
    // occurrences of a pair of characters
    let length = 0;
 
    // Traverse the given string
    for(let k = 0; k < s.length; k++)
    {
        var curr = s.charAt(k);
         
        // If current character is same
        // as the required character
        if (curr == required)
        {
             
            // Increase length by 1
            length += 1;
 
            // Reset required character
            if (required == i)
                required = j;
            else
                required = i;
        }
    }
 
    // Return the length
    return length;
}
 
// Function to find minimum characters
// required to be deleted from S to
// obtain an alternating sequence
function minimumDeletions( S)
{
     
    // Stores maximum length
    // of alternating sequence
    // of two characters
    let len = 0;
 
    // Stores length of the string
    let n = S.length;
 
    // Generate every pair
    // of English alphabets
    for(let i = 0; i < 26; i++)
    {
        for(let j = i + 1; j < 26; j++)
        {
             
            // Function call to find length
            // of alternating sequence for
            // current pair of characters
            let newLen =
            findLength(S, String.fromCharCode(i + 97),
                          String.fromCharCode(j + 97));
 
            // Update len to store the maximum
            // of len and newLen in len
            len = Math.max(len, newLen);
        }
    }
 
    // Return n - len as the final result
    return n - len;
}
 
// Driver Code
 
// Given Input
let S = "adebbeeaebd";
     
// Function call to find minimum
// characters required to be removed
// from S to make it an alternating
// sequence of a pair of characters
document.write(minimumDeletions(S));
 
     
     
</script>
Producción: 

7

 

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

Publicación traducida automáticamente

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