Dada una string str de longitud N (divisible por 3) que consta de al menos tres caracteres distintos, la tarea es encontrar la longitud de la substring más pequeña cuyos caracteres se pueden reemplazar para que cada carácter aparezca exactamente N/3 veces.
Ejemplos:
Entrada: str = “ABB”
Salida: 1
Explicación: Una forma óptima es reemplazar la substring “B” con cualquier carácter, supongamos “C”.
Por lo tanto, el resultado es «ABC» que tiene la frecuencia de cada carácter como N/3.Entrada: str = “ABCBBB”
Salida: 2
Enfoque: El problema planteado se puede resolver utilizando la técnica de la ventana deslizante . Dado que la frecuencia de cada carácter debe ser N/3 , se puede calcular el número de ocurrencias en exceso de los caracteres. La idea es encontrar la longitud de la substring más pequeña de modo que contenga todos los caracteres en exceso que luego puedan reemplazarse. A continuación se detallan los pasos a seguir:
- Cree un mapa , extraChars , que almacena los caracteres en str que aparecen más de N/3 veces junto con su respectivo recuento en exceso.
- Use la ventana deslizante para encontrar la substring más corta que tenga todos los caracteres en extraChar con la frecuencia dada. Se puede hacer de manera similar a como se discutió en el problema de encontrar la substring más pequeña que contiene todos los caracteres de otra string .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int balanceString(string str){
int N = str.length();
// If length of str is 0
if (N == 0) {
return 0;
}
// Stores the frequency of
// each char in str
map<char, int> strFreq;
for (char c : str)
strFreq++;
// Stores the characters having
// excess occurrences with count
map<char, int> extraChars;
for (auto c : strFreq) {
// If there are more than N/3
// characters in the string str
if (c.second > N / 3)
extraChars = (c.second - N / 3);
}
// If no characters occurs more
// than N/3 time in the string
if (extraChars.size() == 0) {
return 0;
}
// Represents start of the window,
// end of the window and the
// required answer respectively
int i = 0, j = 0;
int minWindowLength = N + 1;
// Stores the number of unique
// characters to in substring
int count = extraChars.size();
while (j < N) {
// Store current character
char c = str[j];
// Check if c is an excess char
if (extraChars.find(c) != extraChars.end()) {
// Reduce Count
extraChars--;
// If window has the
// required count
if (extraChars == 0)
count--;
}
// If current window has all char
if (count == 0) {
// Reduce Window size
while (i < N && count == 0) {
// Update the minimum
// length of window
minWindowLength = min(minWindowLength, j - i + 1);
// If character at index
// i is an excess char
if (extraChars.find(str[i]) != extraChars.end()) {
// Update frequency
extraChars[str[i]]++;
// Update Count
if (extraChars[str[i]] == 1)
count++;
}
i++;
}
}
j++;
}
return minWindowLength;
}
// Driver Code
int main() {
string str = "ABCBBB";
cout << balanceString(str);
return 0;
}
// This code is contributed by hrithikgarg03188
Java
// Java code to implement above approach
import java.io.*;
import java.util.*;
class GFG {
static int balanceString(String str)
{
int N = str.length();
// If length of str is 0
if (N == 0) {
return 0;
}
// Stores the frequency of
// each char in str
HashMap<Character, Integer> strFreq
= new HashMap<>();
for (char c : str.toCharArray())
strFreq.put(c,
strFreq.getOrDefault(c, 0)
+ 1);
// Stores the characters having
// excess occurrences with count
HashMap<Character, Integer> extraChars
= new HashMap<>();
for (char c : strFreq.keySet()) {
// If there are more than N/3
// characters in the string str
if (strFreq.get(c) > N / 3)
extraChars.put(c,
strFreq.get(c)
- N / 3);
}
// If no characters occurs more
// than N/3 time in the string
if (extraChars.size() == 0) {
return 0;
}
// Represents start of the window,
// end of the window and the
// required answer respectively
int i = 0, j = 0;
int minWindowLength = N + 1;
// Stores the number of unique
// characters to in substring
int count = extraChars.size();
while (j < N) {
// Store current character
char c = str.charAt(j);
// Check if c is an excess char
if (extraChars.containsKey(c)) {
// Reduce Count
extraChars.put(c,
extraChars.get(c)
- 1);
// If window has the
// required count
if (extraChars.get(c) == 0)
count--;
}
// If current window has all char
if (count == 0) {
// Reduce Window size
while (i < N && count == 0) {
// Update the minimum
// length of window
minWindowLength
= Math.min(minWindowLength,
j - i + 1);
// If character at index
// i is an excess char
if (extraChars.containsKey(
str.charAt(i))) {
// Update frequency
extraChars.put(
str.charAt(i),
extraChars.get(
str.charAt(i))
+ 1);
// Update Count
if (extraChars.get(
str.charAt(i))
== 1)
count++;
}
i++;
}
}
j++;
}
return minWindowLength;
}
// Driver Code
public static void main(String[] args)
{
String str = "ABCBBB";
System.out.println(balanceString(str));
}
}
Python3
# python3 code for the above approach
def balanceString(str):
N = len(str)
# If length of str is 0
if (N == 0):
return 0
# Stores the frequency of
# each char in str
strFreq = {}
for c in str:
strFreq = strFreq + 1 if c in strFreq else 1
# Stores the characters having
# excess occurrences with count
extraChars = {}
for c in strFreq:
# If there are more than N/3
# characters in the string str
if (strFreq > N // 3):
extraChars = (strFreq - N // 3)
# If no characters occurs more
# than N/3 time in the string
if (len(extraChars) == 0):
return 0
# Represents start of the window,
# end of the window and the
# required answer respectively
i, j = 0, 0
minWindowLength = N + 1
# Stores the number of unique
# characters to in substring
count = len(extraChars)
while (j < N):
# Store current character
c = str[j]
# Check if c is an excess char
if (c in extraChars):
# Reduce Count
extraChars -= 1
# If window has the
# required count
if (extraChars == 0):
count -= 1
# If current window has all char
if (count == 0):
# Reduce Window size
while (i < N and count == 0):
# Update the minimum
# length of window
minWindowLength = min(minWindowLength, j - i + 1)
# If character at index
# i is an excess char
if (str[i] in extraChars):
# Update frequency
extraChars[str[i]] += 1
# Update Count
if (extraChars[str[i]] == 1):
count += 1
i += 1
j += 1
return minWindowLength
# Driver Code
if __name__ == "__main__":
str = "ABCBBB"
print(balanceString(str))
# This code is contributed by rakeshsahni
C#
// Java code to implement above approach
using System;
using System.Collections.Generic;
class GFG {
static int balanceString(string str)
{
int N = str.Length;
// If length of str is 0
if (N == 0) {
return 0;
}
// Stores the frequency of
// each char in str
Dictionary<char, int> strFreq
= new Dictionary<char, int>();
foreach(char c in str.ToCharArray())
{
if (strFreq.ContainsKey(c))
strFreq += 1;
else
strFreq = 1;
}
// Stores the characters having
// excess occurrences with count
Dictionary<char, int> extraChars
= new Dictionary<char, int>();
foreach(KeyValuePair<char, int> c in strFreq)
{
// If there are more than N/3
// characters in the string str
if (c.Value > N / 3)
extraChars = c.Value - N / 3;
}
// If no characters occurs more
// than N/3 time in the string
if (extraChars.Count == 0) {
return 0;
}
// Represents start of the window,
// end of the window and the
// required answer respectively
int i = 0, j = 0;
int minWindowLength = N + 1;
// Stores the number of unique
// characters to in substring
int count = extraChars.Count;
while (j < N) {
// Store current character
char c = str[j];
// Check if c is an excess char
if (extraChars.ContainsKey(c)) {
// Reduce Count
extraChars -= 1;
// If window has the
// required count
if (extraChars == 0)
count--;
}
// If current window has all char
if (count == 0) {
// Reduce Window size
while (i < N && count == 0) {
// Update the minimum
// length of window
minWindowLength = Math.Min(
minWindowLength, j - i + 1);
// If character at index
// i is an excess char
if (extraChars.ContainsKey(str[i])) {
// Update frequency
extraChars[str[i]] += 1;
// Update Count
if (extraChars[str[i]] == 1)
count++;
}
i++;
}
}
j++;
}
return minWindowLength;
}
// Driver Code
public static void Main()
{
string str = "ABCBBB";
Console.WriteLine(balanceString(str));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
function balanceString(str) {
let N = str.length;
// If length of str is 0
if (N == 0) {
return 0;
}
// Stores the frequency of
// each char in str
let strFreq
= new Map();
str = str.split('')
for (let c of str) {
if (strFreq.has(c))
strFreq.set(c,
strFreq.get(c)
+ 1);
else
strFreq.set(c, 1)
}
str = str.join('')
// Stores the characters having
// excess occurrences with count
let extraChars
= new Map();
for (let c of strFreq.keys()) {
// If there are more than N/3
// characters in the string str
if (strFreq.get(c) > Math.floor(N / 3))
extraChars.set(c,
strFreq.get(c)
- Math.floor(N / 3));
}
// If no characters occurs more
// than N/3 time in the string
if (extraChars.size == 0) {
return 0;
}
// Represents start of the window,
// end of the window and the
// required answer respectively
let i = 0, j = 0;
let minWindowLength = N + 1;
// Stores the number of unique
// characters to in substring
let count = extraChars.size;
while (j < N) {
// Store current character
let c = str.charAt(j);
// Check if c is an excess char
if (extraChars.has(c)) {
// Reduce Count
extraChars.set(c,
extraChars.get(c)
- 1);
// If window has the
// required count
if (extraChars.get(c) == 0)
count--;
}
// If current window has all char
if (count == 0) {
// Reduce Window size
while (i < N && count == 0) {
// Update the minimum
// length of window
minWindowLength
= Math.min(minWindowLength,
j - i + 1);
// If character at index
// i is an excess char
if (extraChars.has(
str.charAt(i))) {
// Update frequency
extraChars.set(
str.charAt(i),
extraChars.get(
str.charAt(i))
+ 1);
// Update Count
if (extraChars.get(
str.charAt(i))
== 1)
count++;
}
i++;
}
}
j++;
}
return minWindowLength;
}
// Driver Code
let str = "ABCBBB";
document.write(balanceString(str));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA