Dada una string S que consta solo de ‘X’ , ‘Y’ y ‘Z’ , la tarea es convertir S en una string que consta de un solo carácter distinto seleccionando un carácter y eliminando las substrings que no contienen ese carácter, como mínimo numero de veces.
Nota: Una vez que se elige un carácter, no se puede utilizar ningún otro carácter en operaciones posteriores.
Ejemplos:
Entrada: S = “XXX”
Salida: 0
Explicación: Dado que la string dada ya consta de un único carácter distinto, es decir, X, no es necesario eliminarla. Por lo tanto, el conteo requerido es 0.Entrada: S = “XYZXYZX”
Salida: 2
Explicación:
Seleccionar el carácter ‘X’ y eliminar las substrings “YZ” en dos operaciones consecutivas reduce la string a “XXX”, que consta de un solo carácter distinto.
Enfoque: la idea es contar las ocurrencias de cada carácter usando unordered_map y contar el número de eliminaciones requeridas para cada uno de ellos e imprimir el mínimo. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa_desordenado y almacene los índices de ocurrencias para cada uno de los caracteres.
- Itere sobre todos los caracteres de la string S y actualice las apariciones de los caracteres ‘X’, ‘Y’ y ‘Z’ en el mapa .
- Itere sobre el Mapa y para cada personaje, cuente el número de eliminaciones requeridas para cada personaje.
- Después de calcular para cada carácter, imprima el recuento mínimo obtenido para cualquiera de los caracteres.
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 minimum removals
// required to convert given string
// to single distinct characters only
int minimumOperations(string s, int n)
{
// Unordered map to store positions
// of characters X, Y and Z
unordered_map<char, vector<int> > mp;
// Update indices of X, Y, Z;
for (int i = 0; i < n; i++) {
mp[s[i]].push_back(i);
}
// Stores the count of
// minimum removals
int ans = INT_MAX;
// Traverse the Map
for (auto x : mp) {
int curr = 0;
int prev = 0;
bool first = true;
// Count the number of removals
// required for current character
for (int index : (x.second)) {
if (first) {
if (index > 0) {
curr++;
}
prev = index;
first = false;
}
else {
if (index != prev + 1) {
curr++;
}
prev = index;
}
}
if (prev != n - 1) {
curr++;
}
// Update the answer
ans = min(ans, curr);
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
// Given string
string s = "YYXYZYXYZXY";
// Size of string
int N = s.length();
// Function call
minimumOperations(s, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find minimum removals
// required to convert given string
// to single distinct characters only
static void minimumOperations(String s, int n)
{
// Unordered map to store positions
// of characters X, Y and Z
HashMap<Character, List<Integer>> mp = new HashMap<>();
// Update indices of X, Y, Z;
for(int i = 0; i < n; i++)
{
if (mp.containsKey(s.charAt(i)))
{
mp.get(s.charAt(i)).add(i);
}
else
{
mp.put(s.charAt(i), new ArrayList<Integer>(Arrays.asList(i)));
}
}
// Stores the count of
// minimum removals
int ans = Integer.MAX_VALUE;
// Traverse the Map
for (Map.Entry<Character, List<Integer>> x : mp.entrySet())
{
int curr = 0;
int prev = 0;
boolean first = true;
// Count the number of removals
// required for current character
for(Integer index : (x.getValue()))
{
if (first)
{
if (index > 0)
{
curr++;
}
prev = index;
first = false;
}
else
{
if (index != prev + 1)
{
curr++;
}
prev = index;
}
}
if (prev != n - 1)
{
curr++;
}
// Update the answer
ans = Math.min(ans, curr);
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main(String[] args)
{
// Given string
String s = "YYXYZYXYZXY";
// Size of string
int N = s.length();
// Function call
minimumOperations(s, N);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
import sys;
INT_MAX = sys.maxsize;
# Function to find minimum removals
# required to convert given string
# to single distinct characters only
def minimumOperations(s, n) :
# Unordered map to store positions
# of characters X, Y and Z
mp = {};
# Update indices of X, Y, Z;
for i in range(n) :
if s[i] in mp :
mp[s[i]].append(i);
else :
mp[s[i]] = [i];
# Stores the count of
# minimum removals
ans = INT_MAX;
# Traverse the Map
for x in mp :
curr = 0;
prev = 0;
first = True;
# Count the number of removals
# required for current character
for index in mp[x] :
if (first) :
if (index > 0) :
curr += 1;
prev = index;
first = False;
else :
if (index != prev + 1) :
curr += 1;
prev = index;
if (prev != n - 1) :
curr += 1;
# Update the answer
ans = min(ans, curr);
# Print the answer
print(ans);
# Driver Code
if __name__ == "__main__" :
# Given string
s = "YYXYZYXYZXY";
# Size of string
N = len(s);
# Function call
minimumOperations(s, N);
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum removals
// required to convert given string
// to single distinct characters only
static void minimumOperations(string s, int n)
{
// Unordered map to store positions
// of characters X, Y and Z
Dictionary<char,
List<int>> mp = new Dictionary<char,
List<int>>();
// Update indices of X, Y, Z;
for(int i = 0; i < n; i++)
{
if (mp.ContainsKey(s[i]))
{
mp[s[i]].Add(i);
}
else
{
mp[s[i]] = new List<int>();
mp[s[i]].Add(i);
}
}
// Stores the count of
// minimum removals
int ans = Int32.MaxValue;
// Traverse the Map
foreach(KeyValuePair<char, List<int>> x in mp)
{
int curr = 0;
int prev = 0;
bool first = true;
// Count the number of removals
// required for current character
foreach(int index in (x.Value))
{
if (first)
{
if (index > 0)
{
curr++;
}
prev = index;
first = false;
}
else
{
if (index != prev + 1)
{
curr++;
}
prev = index;
}
}
if (prev != n - 1)
{
curr++;
}
// Update the answer
ans = Math.Min(ans, curr);
}
// Print the answer
Console.Write(ans);
}
// Driver Code
static void Main()
{
// Given string
string s = "YYXYZYXYZXY";
// Size of string
int N = s.Length;
// Function call
minimumOperations(s, N);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program for the above approach
// Function to find minimum removals
// required to convert given string
// to single distinct characters only
function minimumOperations(s, n)
{
// Unordered map to store positions
// of characters X, Y and Z
var mp = {};
// Update indices of X, Y, Z;
for (var i = 0; i < n; i++) {
if (mp.hasOwnProperty(s[i])) {
mp[s[i]].push(i);
} else {
mp[s[i]] = [];
mp[s[i]].push(i);
}
}
// Stores the count of
// minimum removals
var ans = 2147483647;
// Traverse the Map
for (const [key, value] of Object.entries(mp)) {
var curr = 0;
var prev = 0;
var first = true;
// Count the number of removals
// required for current character
for (const index of value) {
if (first) {
if (index > 0) {
curr++;
}
prev = index;
first = false;
} else {
if (index !== prev + 1) {
curr++;
}
prev = index;
}
}
if (prev !== n - 1) {
curr++;
}
// Update the answer
ans = Math.min(ans, curr);
}
// Print the answer
document.write(ans);
}
// Driver Code
// Given string
var s = "YYXYZYXYZXY";
// Size of string
var N = s.length;
// Function call
minimumOperations(s, N);
// This code is contributed by rdtank.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA