Dadas dos strings A y B. Minimice el número de caracteres únicos en la string A intercambiando A[i] con B[i] o manteniéndolo sin cambios. El número de intercambios puede ser mayor o igual a 0. Tenga en cuenta que A[i] solo se puede intercambiar con el mismo elemento de índice en B. Imprima el número mínimo de caracteres únicos. Restricciones: 0 < longitud de A ≤ 15.
Ejemplos:
Input : A = ababa
B = babab
Output : 1
Swapping all b's in string A, with
a's in string B results in string
A having all characters as a.
Input : A = abaaa
B = bbabb
Output : 2
Initially string A has 2 unique
characters. Swapping at any index
does not change this count.
Enfoque: El problema se puede resolver usando backtracking . Cree un mapa en el que la clave sea A[i] y el valor sea el recuento del carácter correspondiente. El tamaño del mapa indica el número de caracteres distintos, ya que solo los elementos que están presentes en la string A están presentes como clave en el mapa. En cada posición del índice, hay dos opciones: intercambiar A[i] con B[i] o mantener A[i] sin cambios. Comience desde el índice 0 y haga lo siguiente para cada índice:
- Mantenga A[i] sin cambios, incremente el recuento de A[i] en uno en el mapa y llame recursivamente para el siguiente índice.
- Retroceda disminuyendo el conteo de A[i] en uno, intercambie A[i] con B[i], incremente el conteo de A[i] en uno en el mapa y nuevamente llame recursivamente al siguiente índice.
Mantenga una variable ans para almacenar el valor mínimo general de distintos caracteres. En los dos casos mencionados anteriormente, cuando se atraviesa la string completa, compare el número actual de caracteres distintos con el mínimo general en ans y actualice ans en consecuencia.
Implementación:
// CPP program to minimize number of
// unique characters in a string.
#include <bits/stdc++.h>
using namespace std;
// Utility function to find minimum
// number of unique characters in string.
void minCountUtil(string A, string B,
unordered_map<char, int>& ele,
int& ans, int ind)
{
// If entire string is traversed, then
// compare current number of distinct
// characters in A with overall minimum.
if (ind == A.length()) {
ans = min(ans, (int)ele.size());
return;
}
// swap A[i] with B[i], increase count of
// corresponding character in map and call
// recursively for next index.
swap(A[ind], B[ind]);
ele[A[ind]]++;
minCountUtil(A, B, ele, ans, ind + 1);
// Backtrack (Undo the changes done)
ele[A[ind]]--;
// If count of character is reduced to zero,
// then that character is not present in A.
// So remove that character from map.
if (ele[A[ind]] == 0)
ele.erase(A[ind]);
// Restore A to original form.
// (Backtracking step)
swap(A[ind], B[ind]);
// Increase count of A[i] in map and
// call recursively for next index.
ele[A[ind]]++;
minCountUtil(A, B, ele, ans, ind + 1);
// Restore the changes done
// (Backtracking step)
ele[A[ind]]--;
if (ele[A[ind]] == 0)
ele.erase(A[ind]);
}
// Function to find minimum number of
// distinct characters in string.
int minCount(string A, string B)
{
// Variable to store minimum number
// of distinct character.
// Initialize it with length of A
// as maximum possible value is
// length of A.
int ans = A.length();
// Map to store count of distinct
// characters in A. To keep
// complexity of insert operation
// constant unordered_map is used.
unordered_map<char, int> ele;
// Call utility function to find
// minimum number of unique
// characters.
minCountUtil(A, B, ele, ans, 0);
return ans;
}
int main()
{
string A = "abaaa";
string B = "bbabb";
cout << minCount(A, B);
return 0;
}
2
Complejidad temporal: O(2 n )
Espacio auxiliar: O(n)