Dada una string S de alfabetos ingleses en minúsculas, la tarea es encontrar el número mínimo de caracteres que se cambiarán de modo que la rotación izquierda y derecha de la string sea la misma.
Ejemplos:
Entrada: S = “abcd”
Salida: 2
Explicación:
String después del desplazamiento a la izquierda: “bcda”
String después del desplazamiento a la derecha: “dabc”
Cambiando el carácter en la posición 3 a ‘a’ y el carácter en la posición 4 a ‘b’, la string se modifica a «abab».
Por lo tanto, tanto la rotación hacia la izquierda como hacia la derecha se convierte en «baba».Entrada: S = “gfg”
Salida: 1
Explicación:
Después de actualizar el carácter en la posición 1 a ‘g’, la string se convierte en “ggg”.
Por lo tanto, la rotación izquierda y derecha son iguales.
Enfoque: la observación clave para resolver el problema es que cuando la longitud de la string es par, entonces todos los caracteres en el índice par y los caracteres en el índice impar deben ser iguales para que las rotaciones izquierda y derecha sean iguales. Para strings de longitud impar, todos los caracteres deben ser iguales. Siga los pasos a continuación para resolver el problema:
- Compruebe si la longitud de la string es par, entonces el número mínimo de caracteres que se cambiará es la longitud de la string, excluyendo la frecuencia del elemento que aparece más en los índices pares e impares.
- De lo contrario, si la longitud de la string es impar, el número mínimo de caracteres que se cambiará es la longitud de la string, excluyendo la frecuencia del carácter que aparece más en la string.
- Imprime el conteo final obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// characters to be removed from
// the string
int getMinimumRemoval(string str)
{
int n = str.length();
// Initialize answer by N
int ans = n;
// If length is even
if (n % 2 == 0) {
// Frequency array for odd
// and even indices
vector<int> freqEven(128);
vector<int> freqOdd(128);
// Store the frequency of the
// characters at even and odd
// indices
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
freqEven[str[i]]++;
}
else {
freqOdd[str[i]]++;
}
}
// Stores the most occurring frequency
// for even and odd indices
int evenMax = 0, oddMax = 0;
for (char chr = 'a'; chr <= 'z'; chr++) {
evenMax = max(evenMax, freqEven[chr]);
oddMax = max(oddMax, freqOdd[chr]);
}
// Update the answer
ans = ans - evenMax - oddMax;
}
// If length is odd
else {
// Stores the frequency of the
// characters of the string
vector<int> freq(128);
for (int i = 0; i < n; i++) {
freq[str[i]]++;
}
// Stores the most occurring character
// in the string
int strMax = 0;
for (char chr = 'a'; chr <= 'z'; chr++) {
strMax = max(strMax, freq[chr]);
}
// Update the answer
ans = ans - strMax;
}
return ans;
}
// Driver Code
int main()
{
string str = "geeksgeeks";
cout << getMinimumRemoval(str);
}
Java
// Java program of the
// above approach
class GFG{
// Function to find the minimum
// characters to be removed from
// the string
public static int getMinimumRemoval(String str)
{
int n = str.length();
// Initialize answer by N
int ans = n;
// If length is even
if (n % 2 == 0)
{
// Frequency array for odd
// and even indices
int[] freqEven = new int[128];
int[] freqOdd = new int[128];
// Store the frequency of the
// characters at even and odd
// indices
for(int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
freqEven[str.charAt(i)]++;
}
else
{
freqOdd[str.charAt(i)]++;
}
}
// Stores the most occurring frequency
// for even and odd indices
int evenMax = 0, oddMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
evenMax = Math.max(evenMax,
freqEven[chr]);
oddMax = Math.max(oddMax,
freqOdd[chr]);
}
// Update the answer
ans = ans - evenMax - oddMax;
}
// If length is odd
else
{
// Stores the frequency of the
// characters of the string
int[] freq = new int[128];
for(int i = 0; i < n; i++)
{
freq[str.charAt(i)]++;
}
// Stores the most occurring character
// in the string
int strMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
strMax = Math.max(strMax, freq[chr]);
}
// Update the answer
ans = ans - strMax;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String str = "geeksgeeks";
System.out.print(getMinimumRemoval(str));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 Program of the
# above approach
# Function to find the minimum
# characters to be removed from
# the string
def getMinimumRemoval(str):
n = len(str)
# Initialize answer by N
ans = n
# If length is even
if(n % 2 == 0):
# Frequency array for odd
# and even indices
freqEven = {}
freqOdd = {}
for ch in range(ord('a'),
ord('z') + 1):
freqEven[chr(ch)] = 0
freqOdd[chr(ch)] = 0
# Store the frequency of the
# characters at even and odd
# indices
for i in range(n):
if(i % 2 == 0):
if str[i] in freqEven:
freqEven[str[i]] += 1
else:
if str[i] in freqOdd:
freqOdd[str[i]] += 1
# Stores the most occurring
# frequency for even and
# odd indices
evenMax = 0
oddMax = 0
for ch in range(ord('a'),
ord('z') + 1):
evenMax = max(evenMax,
freqEven[chr(ch)])
oddMax = max(oddMax,
freqOdd[chr(ch)])
# Update the answer
ans = ans - evenMax - oddMax
# If length is odd
else:
# Stores the frequency of the
# characters of the string
freq = {}
for ch in range('a','z'):
freq[chr(ch)] = 0
for i in range(n):
if str[i] in freq:
freq[str[i]] += 1
# Stores the most occurring
# characterin the string
strMax = 0
for ch in range('a','z'):
strMax = max(strMax,
freq[chr(ch)])
# Update the answer
ans = ans - strMax
return ans
# Driver Code
str = "geeksgeeks"
print(getMinimumRemoval(str))
# This code is contributed by avanitrachhadiya2155
C#
// C# program of the
// above approach
using System;
class GFG{
// Function to find the minimum
// characters to be removed from
// the string
public static int getMinimumRemoval(String str)
{
int n = str.Length;
// Initialize answer by N
int ans = n;
// If length is even
if (n % 2 == 0)
{
// Frequency array for odd
// and even indices
int[] freqEven = new int[128];
int[] freqOdd = new int[128];
// Store the frequency of the
// characters at even and odd
// indices
for(int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
freqEven[str[i]]++;
}
else
{
freqOdd[str[i]]++;
}
}
// Stores the most occurring frequency
// for even and odd indices
int evenMax = 0, oddMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
evenMax = Math.Max(evenMax,
freqEven[chr]);
oddMax = Math.Max(oddMax,
freqOdd[chr]);
}
// Update the answer
ans = ans - evenMax - oddMax;
}
// If length is odd
else
{
// Stores the frequency of the
// characters of the string
int[] freq = new int[128];
for(int i = 0; i < n; i++)
{
freq[str[i]]++;
}
// Stores the most occurring character
// in the string
int strMax = 0;
for(char chr = 'a'; chr <= 'z'; chr++)
{
strMax = Math.Max(strMax, freq[chr]);
}
// Update the answer
ans = ans - strMax;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
String str = "geeksgeeks";
Console.Write(getMinimumRemoval(str));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program of the
// above approach
// Function to find the minimum
// characters to be removed from
// the string
function getMinimumRemoval(str) {
var n = str.length;
// Initialize answer by N
var ans = n;
// If length is even
if (n % 2 === 0) {
// Frequency array for odd
// and even indices
var freqEven = new Array(128).fill(0);
var freqOdd = new Array(128).fill(0);
// Store the frequency of the
// characters at even and odd
// indices
for (var i = 0; i < n; i++) {
if (i % 2 === 0) {
freqEven[str[i].charCodeAt(0)]++;
} else {
freqOdd[str[i].charCodeAt(0)]++;
}
}
// Stores the most occuring frequency
// for even and odd indices
var evenMax = 0,
oddMax = 0;
for (var chr = "a".charCodeAt(0); chr <= "z".charCodeAt(0); chr++) {
evenMax = Math.max(evenMax, freqEven[chr]);
oddMax = Math.max(oddMax, freqOdd[chr]);
}
// Update the answer
ans = ans - evenMax - oddMax;
}
// If length is odd
else {
// Stores the frequency of the
// characters of the string
var freq = new Array(128).fill(0);
for (var i = 0; i < n; i++) {
freq[str[i].charCodeAt(0)]++;
}
// Stores the most occuring character
// in the string
var strMax = 0;
for (var chr = "a".charCodeAt(0); chr <= "z".charCodeAt(0); chr++) {
strMax = Math.max(strMax, freq[chr]);
}
// Update the answer
ans = ans - strMax;
}
return ans;
}
// Driver code
var str = "geeksgeeks";
document.write(getMinimumRemoval(str));
</script>
Producción:
6
Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.