Dada una string str , la tarea es hacer que la string comience y termine en el mismo carácter con el número mínimo de operaciones dadas. En una sola operación, se puede eliminar cualquier carácter de la string. Tenga en cuenta que la longitud de la string resultante debe ser mayor que 1 y no es posible imprimir -1 .
Ejemplos:
Entrada: str = «geeksforgeeks»
Salida: 3
Elimine el primero y los últimos dos caracteres
y la string se convierte en «eeksforgee»
Entrada: str = «abcda»
Salida: 0
Enfoque: si la string debe comenzar y terminar en un carácter, digamos ch, entonces una forma óptima es eliminar todos los caracteres antes de la primera aparición de ch y todos los caracteres después de la última aparición de ch . Encuentre la cantidad de caracteres que deben eliminarse para cada valor posible de ch desde ‘a’ hasta ‘z’ y elija el que tenga la cantidad mínima de operaciones de eliminación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 26;
// Function to return the minimum
// operations required
int minOperation(string str, int len)
{
// To store the first and the last
// occurrence of all the characters
int first[MAX], last[MAX];
// Set the first and the last occurrence
// of all the characters to -1
for (int i = 0; i < MAX; i++) {
first[i] = -1;
last[i] = -1;
}
// Update the occurrences of the characters
for (int i = 0; i < len; i++) {
int index = (str[i] - 'a');
// Only set the first occurrence if
// it hasn't already been set
if (first[index] == -1)
first[index] = i;
last[index] = i;
}
// To store the minimum operations
int minOp = -1;
for (int i = 0; i < MAX; i++) {
// If the frequency of the current
// character in the string
// is less than 2
if (first[i] == -1 || first[i] == last[i])
continue;
// Count of characters to be
// removed so that the string
// starts and ends at the
// current character
int cnt = len - (last[i] - first[i] + 1);
if (minOp == -1 || cnt < minOp)
minOp = cnt;
}
return minOp;
}
// Driver code
int main()
{
string str = "abcda";
int len = str.length();
cout << minOperation(str, len);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int MAX = 26;
// Function to return the minimum
// operations required
static int minOperation(String str, int len)
{
// To store the first and the last
// occurrence of all the characters
int first[] = new int[MAX];
int last[] = new int[MAX];
// Set the first and the last occurrence
// of all the characters to -1
for (int i = 0; i < MAX; i++)
{
first[i] = -1;
last[i] = -1;
}
// Update the occurrences of the characters
for (int i = 0; i < len; i++)
{
int index = (str.charAt(i) - 'a');
// Only set the first occurrence if
// it hasn't already been set
if (first[index] == -1)
first[index] = i;
last[index] = i;
}
// To store the minimum operations
int minOp = -1;
for (int i = 0; i < MAX; i++)
{
// If the frequency of the current
// character in the string
// is less than 2
if (first[i] == -1 ||
first[i] == last[i])
continue;
// Count of characters to be
// removed so that the string
// starts and ends at the
// current character
int cnt = len - (last[i] - first[i] + 1);
if (minOp == -1 || cnt < minOp)
minOp = cnt;
}
return minOp;
}
// Driver code
public static void main (String[] args)
{
String str = "abcda";
int len = str.length();
System.out.println(minOperation(str, len));
}
}
// This code is contributed by AnkitRai01
Python3
# Python implementation of the approach
MAX = 26;
# Function to return the minimum
# operations required
def minOperation(str, len):
# To store the first and the last
# occurrence of all the characters
first, last = [0] * MAX, [0] * MAX;
# Set the first and the last occurrence
# of all the characters to -1
for i in range(MAX):
first[i] = -1;
last[i] = -1;
# Update the occurrences of the characters
for i in range(len):
index = (ord(str[i]) - ord('a'));
# Only set the first occurrence if
# it hasn't already been set
if (first[index] == -1):
first[index] = i;
last[index] = i;
# To store the minimum operations
minOp = -1;
for i in range(MAX):
# If the frequency of the current
# character in the string
# is less than 2
if (first[i] == -1 or first[i] == last[i]):
continue;
# Count of characters to be
# removed so that the string
# starts and ends at the
# current character
cnt = len - (last[i] - first[i] + 1);
if (minOp == -1 or cnt < minOp):
minOp = cnt;
return minOp;
# Driver code
str = "abcda";
len = len(str);
print( minOperation(str, len));
# This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
readonly static int MAX = 26;
// Function to return the minimum
// operations required
static int minOperation(String str, int len)
{
// To store the first and the last
// occurrence of all the characters
int []first = new int[MAX];
int []last = new int[MAX];
// Set the first and the last occurrence
// of all the characters to -1
for (int i = 0; i < MAX; i++)
{
first[i] = -1;
last[i] = -1;
}
// Update the occurrences of the characters
for (int i = 0; i < len; i++)
{
int index = (str[i] - 'a');
// Only set the first occurrence if
// it hasn't already been set
if (first[index] == -1)
first[index] = i;
last[index] = i;
}
// To store the minimum operations
int minOp = -1;
for (int i = 0; i < MAX; i++)
{
// If the frequency of the current
// character in the string
// is less than 2
if (first[i] == -1 ||
first[i] == last[i])
continue;
// Count of characters to be
// removed so that the string
// starts and ends at the
// current character
int cnt = len - (last[i] - first[i] + 1);
if (minOp == -1 || cnt < minOp)
minOp = cnt;
}
return minOp;
}
// Driver code
public static void Main (String[] args)
{
String str = "abcda";
int len = str.Length;
Console.WriteLine(minOperation(str, len));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
var MAX = 26;
// Function to return the minimum
// operations required
function minOperation(str, len)
{
// To store the first and the last
// occurrence of all the characters
var first = Array(MAX).fill(-1);
var last = Array(MAX).fill(-1);
// Update the occurrences of the characters
for (var i = 0; i < len; i++) {
var index = (str[i].charCodeAt(0) - 'a'.charCodeAt(0));
// Only set the first occurrence if
// it hasn't already been set
if (first[index] == -1)
first[index] = i;
last[index] = i;
}
// To store the minimum operations
var minOp = -1;
for (var i = 0; i < MAX; i++) {
// If the frequency of the current
// character in the string
// is less than 2
if (first[i] == -1 || first[i] == last[i])
continue;
// Count of characters to be
// removed so that the string
// starts and ends at the
// current character
var cnt = len - (last[i] - first[i] + 1);
if (minOp == -1 || cnt < minOp)
minOp = cnt;
}
return minOp;
}
// Driver code
var str = "abcda";
var len = str.length;
document.write( minOperation(str, len));
</script>
Producción:
0
Complejidad de tiempo: O (len), donde len es la longitud de la string.
Espacio Auxiliar : O(2*26)