Dada una string de cualquier combinación de tres letras ‘a’, ‘b’ y ‘c’, encuentre la longitud de la string más pequeña que se puede obtener aplicando la siguiente operación repetidamente:
Tome dos caracteres distintos adyacentes y reemplácelos con el tercero.
Ejemplos:
Input : cab
Output : 2
We can select any two adjacent letters,
say 'ca' and transform it into 'b', this
leaves us with string 'bb' of length two.
Input : bcab
Output : 1
Selecting 'bc' and transforming it to 'a'
leaves us with 'aab'. We can then select
'ab' and transform it to 'c', giving 'ac'.
This can further be transformed into 'b',
which is of length one.
Una forma ingenua de hacer esto sería encontrar todos los reemplazos posibles y repetir hasta que encontremos la string mínima. Esto llevaría un tiempo exponencial.
Lema : el orden de las letras no afecta la longitud o el valor de la string mínima.
Prueba por inducción
Caso base : tome la string ‘ab’ y ‘ba’, ambas se reducen a ‘c’
Hipótesis inductiva : Todas las strings de longitud <= k se reducen a la misma string suponiendo que el número de ocurrencias de cada letra en cada string es el mismo.
Paso inductivo : tome dos strings de longitud k + 1 que tengan el mismo número de ocurrencias de cada letra. Encuentra un par de letras que sean adyacentes
en ambas strings. Aquí surgen dos casos:
- Nos las arreglamos para encontrar ese par de letras. Entonces podemos reemplazar estas letras con la tercera letra, obteniendo así dos strings de longitud k que tienen las mismas ocurrencias de cada letra, que por hipótesis inductiva se reduce a la misma string. es decir, tenemos ‘abcacb’ y ‘accbba’ y reducimos ‘ac’ en ambas strings, por lo que obtenemos ‘abcbb’ y ‘bcbba’.
- No podemos encontrar ese par. Esto surge cuando todas las letras de la string son iguales. En este caso, las dos strings son iguales, es decir, ‘ccccccc’ y ‘ccccccc’.
Así por inducción hemos probado este lema.
Enfoque de Programación Dinámica: Ahora podemos diseñar una función usando Programación Dinámica para resolver este problema.
C++
// C++ program to find smallest possible length
// of a string of only three characters
#include<bits/stdc++.h>
using namespace std;
// Program to find length of reduced string
// in a string made of three characters.
#define MAX_LEN 110
// To store results of subproblems
int DP[MAX_LEN][MAX_LEN][MAX_LEN];
// A memoized function find result recursively.
// a, b and c are counts of 'a's, 'b's and
// 'c's in str
int length(int a, int b, int c)
{
// If this subproblem is already evaluated
if(a < 0 or b < 0 or c < 0)
if (DP[a][b] != -1)
return DP[a][b];
// If there is only one type of character
if (a == 0 && b == 0)
return (DP[a][b] = c);
if (a == 0 && c == 0)
return (DP[a][b] = b);
if (b == 0 && c == 0)
return (DP[a][b] = a);
// If only two types of characters are present
if (a == 0)
return (DP[a][b] =
length(a + 1, b - 1, c - 1));
if (b == 0)
return (DP[a][b] =
length(a - 1, b + 1, c - 1));
if (c == 0)
return (DP[a][b] =
length(a - 1, b - 1, c + 1));
// If all types of characters are present.
// Try combining all pairs.
return (DP[a][b] =
min(length(a - 1, b - 1, c + 1),
min(length(a - 1, b + 1, c - 1),
length(a + 1, b - 1, c - 1))));
}
// Returns smallest possible length with given
// operation allowed.
int stringReduction(string str)
{
int n = str.length();
// Counting occurrences of three different
// characters 'a', 'b' and 'c' in str
int count[3] = {0};
for (int i=0; i<n; ++i)
count[str[i]-'a']++;
// Initialize DP[][] entries as -1
for (int i = 0; i <= count[0]; ++i)
for (int j = 0; j < count[1]; ++j)
for (int k = 0; k < count[2]; ++k)
DP[i][j][k] = -1;
return length(count[0], count[1], count[2]);
}
// Driver code
int main()
{
string str = "abcbbaacb";
cout << stringReduction(str);
return 0;
}
Java
// Java program to find smallest possible length
// of a string of only three characters
import java.io.*;
class GFG
{
static int MAX_LEN = 110;
// Program to find length of reduced string
// in a string made of three characters.
static int[][][] DP = new int[MAX_LEN][MAX_LEN][MAX_LEN];
// A memoized function find result recursively.
// a, b and c are counts of 'a's, 'b's and
// 'c's in str
static int length(int a, int b, int c)
{
// If this subproblem is already
// evaluated
if(a < 0 || b < 0 || c < 0)
// If this subproblem is already evaluated
if (DP[a][b] != -1)
return DP[a][b];
// If there is only one type of character
if (a == 0 && b == 0)
return (DP[a][b] = c);
if (a == 0 && c == 0)
return (DP[a][b] = b);
if (b == 0 && c == 0)
return (DP[a][b] = a);
// If only two types of characters are present
if (a == 0)
return (DP[a][b] =
length(a + 1, b - 1, c - 1));
if (b == 0)
return (DP[a][b] =
length(a - 1, b + 1, c - 1));
if (c == 0)
return (DP[a][b] =
length(a - 1, b - 1, c + 1));
// If all types of characters are present.
// Try combining all pairs.
DP[a][b] =
Math.min(length(a - 1, b - 1, c + 1),
Math.min(length(a - 1, b + 1, c - 1),
length(a + 1, b - 1, c - 1)));
return DP[a][b];
}
// Returns smallest possible length with given
// operation allowed.
static int stringReduction(String str)
{
int n = str.length();
// Counting occurrences of three different
// characters 'a', 'b' and 'c' in str
int[] count = new int[3];
for (int i = 0; i < n; ++i)
count[str.charAt(i) - 'a']++;
// Initialize DP[][] entries as -1
for (int i = 0; i <= count[0]; ++i)
for (int j = 0; j < count[1]; ++j)
for (int k = 0; k < count[2]; ++k)
DP[i][j][k] = -1;
return length(count[0], count[1], count[2]);
}
// Driver code
public static void main (String[] args) {
String str = "abcbbaacb";
System.out.println(stringReduction(str));
}
}
// This code is contributed by rag2127
Python3
# Python3 program to find smallest possible
# length of a string of only three characters
# A memoized function find result recursively.
# a, b and c are counts of 'a's, 'b's and
# 'c's in str
def length(a, b, c):
global DP
#print(a, b, c)
# If this subproblem is already
# evaluated
if a < 0 or b < 0 or c < 0:
return 0
if (DP[a][b] != -1):
return DP[a][b]
# If there is only one type
# of character
if (a == 0 and b == 0):
DP[a][b] = c
return c
if (a == 0 and c == 0):
DP[a][b] = b
return b
if (b == 0 and c == 0):
DP[a][b] = a
return a
# If only two types of characters
# are present
if (a == 0):
DP[a][b] = length(a + 1, b - 1,
c - 1)
return DP[a][b]
if (b == 0):
DP[a][b] = length(a - 1, b + 1,
c - 1)
return DP[a][b]
if (c == 0):
DP[a][b] = length(a - 1, b - 1,
c + 1)
return DP[a][b]
# If all types of characters are present.
# Try combining all pairs.
x = length(a - 1, b - 1, c + 1)
y = length(a - 1, b + 1, c - 1)
z = length(a + 1, b - 1, c - 1)
DP[a][b] = min([x, y, z])
return DP[a][b]
# Returns smallest possible length with
# given operation allowed.
def stringReduction(str):
n = len(str)
# Counting occurrences of three different
# characters 'a', 'b' and 'c' in str
count = [0] * 3
for i in range(n):
count[ord(str[i]) - ord('a')] += 1
return length(count[0], count[1], count[2])
# Driver code
if __name__ == '__main__':
DP = [[[-1 for i in range(110)]
for i in range(110)]
for i in range(110)]
str = "abcbbaacb"
print(stringReduction(str))
# This code is contributed by mohit kumar 29
C#
// C# program to find smallest possible length
// of a string of only three characters
using System;
public class GFG
{
static int MAX_LEN = 110;
// Program to find length of reduced string
// in a string made of three characters.
static int[,,] DP = new int[MAX_LEN, MAX_LEN, MAX_LEN];
// A memoized function find result recursively.
// a, b and c are counts of 'a's, 'b's and
// 'c's in str
static int length(int a, int b, int c)
{
// If this subproblem is already
// evaluated
if(a < 0 || b < 0 || c < 0)
// If this subproblem is already evaluated
if (DP[a, b, c] != -1)
return DP[a, b, c];
// If there is only one type of character
if (a == 0 && b == 0)
return (DP[a, b, c] = c);
if (a == 0 && c == 0)
return (DP[a, b, c] = b);
if (b == 0 && c == 0)
return (DP[a, b, c] = a);
// If only two types of characters are present
if (a == 0)
return (DP[a, b, c] =
length(a + 1, b - 1, c - 1));
if (b == 0)
return (DP[a, b, c] =
length(a - 1, b + 1, c - 1));
if (c == 0)
return (DP[a, b, c] =
length(a - 1, b - 1, c + 1));
// If all types of characters are present.
// Try combining all pairs.
DP[a, b, c] =
Math.Min(length(a - 1, b - 1, c + 1),
Math.Min(length(a - 1, b + 1, c - 1),
length(a + 1, b - 1, c - 1)));
return DP[a, b, c];
}
// Returns smallest possible length with given
// operation allowed.
static int stringReduction(string str)
{
int n = str.Length;
// Counting occurrences of three different
// characters 'a', 'b' and 'c' in str
int[] count = new int[3];
for (int i = 0; i < n; ++i)
count[str[i] - 'a']++;
// Initialize DP[][] entries as -1
for (int i = 0; i <= count[0]; ++i)
for (int j = 0; j < count[1]; ++j)
for (int k = 0; k < count[2]; ++k)
DP[i, j, k] = -1;
return length(count[0], count[1], count[2]);
}
// Driver code
static public void Main ()
{
string str = "abcbbaacb";
Console.WriteLine(stringReduction(str));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to find smallest possible length
// of a string of only three characters
let MAX_LEN = 110;
// Program to find length of reduced string
// in a string made of three characters.
let DP = new Array(MAX_LEN);
for(let i = 0; i < DP.length; i++)
{
DP[i] = new Array(MAX_LEN);
for(let j = 0; j < DP[i].length; j++)
{
DP[i][j] = new Array(MAX_LEN);
for(let k = 0; k < MAX_LEN; k++)
{
DP[i][j][k] = 0;
}
}
}
// A memoized function find result recursively.
// a, b and c are counts of 'a's, 'b's and
// 'c's in str
function length(a, b, c)
{
// If this subproblem is already
// evaluated
if(a < 0 || b < 0 || c < 0)
// If this subproblem is already evaluated
if (DP[a][b] != -1)
return DP[a][b];
// If there is only one type of character
if (a == 0 && b == 0)
return (DP[a][b] = c);
if (a == 0 && c == 0)
return (DP[a][b] = b);
if (b == 0 && c == 0)
return (DP[a][b] = a);
// If only two types of characters are present
if (a == 0)
return (DP[a][b] =
length(a + 1, b - 1, c - 1));
if (b == 0)
return (DP[a][b] =
length(a - 1, b + 1, c - 1));
if (c == 0)
return (DP[a][b] =
length(a - 1, b - 1, c + 1));
// If all types of characters are present.
// Try combining all pairs.
DP[a][b] =
Math.min(length(a - 1, b - 1, c + 1),
Math.min(length(a - 1, b + 1, c - 1),
length(a + 1, b - 1, c - 1)));
return DP[a][b];
}
// Returns smallest possible length with given
// operation allowed.
function stringReduction(str)
{
let n = str.length;
// Counting occurrences of three different
// characters 'a', 'b' and 'c' in str
let count = new Array(3);
for(let i = 0; i < 3; i++)
{
count[i] = 0;
}
for (let i = 0; i < n; ++i)
count[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// Initialize DP[][] entries as -1
for (let i = 0; i <= count[0]; ++i)
for (let j = 0; j < count[1]; ++j)
for (let k = 0; k < count[2]; ++k)
DP[i][j][k] = -1;
return length(count[0], count[1], count[2]);
}
// Driver code
let str = "abcbbaacb";
document.write(stringReduction(str));
// This code is contributed by unknown2108
</script>
Producción
1
En el peor de los casos, cada letra está presente en 1/3 de toda la string. Esto conduce al espacio auxiliar = O(N 3 ) y la complejidad del tiempo = O(N 3 )
Space Complexity = O(N^3) Time Complexity = O(N^3)
Enfoque Matemático:
Podemos hacerlo mejor que esto usando tres principios fundamentales:
- Si la string no se puede reducir más, entonces todas las letras de la string son iguales.
- La longitud de la string mínima es <= 2 o igual a la longitud de la string original, o 2 <longitud mínima de la string <longitud de la string original nunca es cierta.
- Si cada letra de la string está presente una cantidad impar de veces, después de un paso de reducción, todas estarán presentes una cantidad par de veces. Lo contrario también es cierto, es decir, si cada letra de la string está presente una cantidad par de veces, estará presente una cantidad impar de veces después de un paso de reducción.
Estos se pueden demostrar de la siguiente manera:
- Si hay dos letras diferentes presentes, podemos seleccionarlas y reducir aún más la longitud de la string.
- Prueba por contradicción:
supongamos que tenemos una string reducida de longitud menor que la string original. Por ejemplo, ‘bbbbbbbb’. Entonces esta string debe haberse originado a partir de una string como ‘acbbbbbb’, ‘bbacbbbb’ o cualquier otra combinación de las mismas. En este caso, podríamos haber seleccionado ‘bc’ en lugar de ‘ac’ y reducirlo aún más. - Del paso recursivo anterior, aumentamos una letra en una y disminuimos las otras dos en una. Entonces, si tuviéramos una combinación como (impar, impar, impar), entonces se convertiría en (impar + 1, impar – 1, impar – 1) o (par, par, par). El reverso se muestra de manera similar.
Ahora podemos combinar los principios anteriores.
Si la string consiste en la repetición de la misma letra, su string reducida mínima es ella misma, y la longitud es la longitud de la string.
Ahora, las otras opciones posibles son strings reducidas que tienen una longitud de uno o dos caracteres. Ahora bien, si todos los caracteres están presentes un número par de veces, o un número impar de veces, la única respuesta posible es 2, porque (0, 2, 0) es (par, par, par) mientras que (0, 1, 0) es (par, impar, par) por lo que solo 2 conserva esta uniformidad.
En cualquier otra condición, la respuesta se convierte en 1.
Implementación:
C++
// C++ program to find smallest possible length
// of a string of only three characters
#include<bits/stdc++.h>
using namespace std;
// Returns smallest possible length with given
// operation allowed.
int stringReduction(string str)
{
int n = str.length();
// Counint occurrences of three different
// characters 'a', 'b' and 'c' in str
int count[3] = {0};
for (int i=0; i<n; ++i)
count[str[i]-'a']++;
// If all characters are same.
if (count[0] == n || count[1] == n ||
count[2] == n)
return n;
// If all characters are present even number
// of times or all are present odd number of
// times.
if ((count[0] % 2) == (count[1] % 2) &&
(count[1] % 2) == (count[2] % 2))
return 2;
// Answer is 1 for all other cases.
return 1;
}
// Driver code
int main()
{
string str = "abcbbaacb";
cout << stringReduction(str);
return 0;
}
Java
// Java program to find smallest possible length
// of a string of only three characters
public class GFG {
// Returns smallest possible length with given
// operation allowed.
static int stringReduction(String str) {
int n = str.length();
// Counint occurrences of three different
// characters 'a', 'b' and 'c' in str
int count[] = new int[3];
for (int i = 0; i < n; ++i) {
count[str.charAt(i) - 'a']++;
}
// If all characters are same.
if (count[0] == n || count[1] == n
|| count[2] == n) {
return n;
}
// If all characters are present even number
// of times or all are present odd number of
// times.
if ((count[0] % 2) == (count[1] % 2)
&& (count[1] % 2) == (count[2] % 2)) {
return 2;
}
// Answer is 1 for all other cases.
return 1;
}
// Driver code
public static void main(String[] args) {
String str = "abcbbaacb";
System.out.println(stringReduction(str));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find smallest possible
# length of a string of only three characters
# Returns smallest possible length
# with given operation allowed.
def stringReduction(str):
n = len(str)
# Counint occurrences of three different
# characters 'a', 'b' and 'c' in str
count = [0] * 3
for i in range(n):
count[ord(str[i]) - ord('a')] += 1
# If all characters are same.
if (count[0] == n or count[1] == n or
count[2] == n):
return n
# If all characters are present even number
# of times or all are present odd number of
# times.
if ((count[0] % 2) == (count[1] % 2) and
(count[1] % 2) == (count[2] % 2)):
return 2
# Answer is 1 for all other cases.
return 1
# Driver code
if __name__ == "__main__":
str = "abcbbaacb"
print(stringReduction(str))
# This code is contributed by ita_c
C#
// C# program to find smallest possible length
// of a string of only three characters
using System;
public class GFG {
// Returns smallest possible length with given
// operation allowed.
static int stringReduction(String str) {
int n = str.Length;
// Counint occurrences of three different
// characters 'a', 'b' and 'c' in str
int []count = new int[3];
for (int i = 0; i < n; ++i) {
count[str[i] - 'a']++;
}
// If all characters are same.
if (count[0] == n || count[1] == n
|| count[2] == n) {
return n;
}
// If all characters are present even number
// of times or all are present odd number of
// times.
if ((count[0] % 2) == (count[1] % 2)
&& (count[1] % 2) == (count[2] % 2)) {
return 2;
}
// Answer is 1 for all other cases.
return 1;
}
// Driver code
public static void Main() {
String str = "abcbbaacb";
Console.WriteLine(stringReduction(str));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to find smallest possible length
// of a string of only three characters
// Returns smallest possible length with
// given operation allowed.
function stringReduction($str)
{
$n = strlen($str);
// Counint occurrences of three different
// characters 'a', 'b' and 'c' in str
$count = array_fill(0, 3, 0);
for ($i = 0; $i < $n; ++$i)
$count[ord($str[$i]) - ord('a')]++;
// If all characters are same.
if ($count[0] == $n || $count[1] == $n ||
$count[2] == $n)
return $n;
// If all characters are present even number
// of times or all are present odd number of
// times.
if (($count[0] % 2) == ($count[1] % 2) &&
($count[1] % 2) == ($count[2] % 2))
return 2;
// Answer is 1 for all other cases.
return 1;
}
// Driver code
$str = "abcbbaacb";
print(stringReduction($str));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find smallest
// possible length of a string of only
// three characters
// Returns smallest possible length
// with given operation allowed.
function stringReduction(str)
{
var n = str.length;
// Counvar occurrences of three different
// characters 'a', 'b' and 'c' in str
var count = Array.from({length: 3}, (_, i) => 0);
for(var i = 0; i < n; ++i)
{
count[str.charAt(i).charCodeAt(0) -
'a'.charCodeAt(0)]++;
}
// If all characters are same.
if (count[0] == n ||
count[1] == n ||
count[2] == n)
{
return n;
}
// If all characters are present even number
// of times or all are present odd number of
// times.
if ((count[0] % 2) == (count[1] % 2) &&
(count[1] % 2) == (count[2] % 2))
{
return 2;
}
// Answer is 1 for all other cases.
return 1;
}
// Driver code
var str = "abcbbaacb";
document.write(stringReduction(str));
// This code is contributed by Princi Singh
</script>
Producción
1
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aditya Kamath . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA