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:
- Inicialice una variable, digamos len, para almacenar la longitud máxima de ocurrencias alternas de un par de caracteres.
- 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 .
- 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