Dadas dos strings A y B de longitudes N y M respectivamente, la tarea es encontrar la longitud de la subsecuencia común más larga que puede ser de dos strings si cualquier carácter de la string A puede intercambiarse con cualquier otro carácter de B cualquier número de veces.
Ejemplos:
Entrada: A = “abdeff”, B = “abbet”
Salida: 4
Explicación: Intercambiar A[5] y B[4] modifica A a “abdeft” y B a “abbef”. LCS de las strings dadas es «abef». Por lo tanto, la longitud es 4.Entrada: A = «abcd», B = «ab»
Salida: 2
Explicación: LCS de las strings dadas es «ab». Por lo tanto, la longitud es 2.
Enfoque: la idea se basa en la observación de que si cualquier carácter de la string A puede intercambiarse con cualquier otro carácter de la string B , entonces también es posible intercambiar caracteres dentro de la string A y también dentro de la string B.
Prueba: si se requiere intercambiar los caracteres A[i] y A[j] , tome un elemento temporal en cualquier índice k en la string B . Siga los pasos a continuación para resolver el problema:
- Cambia A[i] por B[k] .
- Cambia B[k] por A[j] .
- Cambia B[k] por A[i] .
De esta forma, los caracteres dentro de una string se pueden intercambiar. Ahora, los elementos se pueden organizar en cualquier orden. Por lo tanto, la idea es encontrar las frecuencias de todos los caracteres presentes en ambas strings y dividirlas por igual.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos freq , de tamaño 26 , para almacenar la frecuencia de cada carácter presente en las strings .
- Recorra las strings A y B y actualice la frecuencia de cada carácter en la array freq[] .
- Inicialice una variable, digamos cnt , para almacenar la longitud requerida.
- Recorra la array freq[] y aumente el valor de cnt en freq[i] / 2 .
- Almacene el mínimo de cnt , N y M en una variable, digamos ans .
- Imprime el valor de ans como resultado.
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 the length of LCS
// possible by swapping any character
// of a string with that of another string
void lcsBySwapping(string A, string B)
{
// Store the size of the strings
int N = A.size();
int M = B.size();
// Stores frequency of characters
int freq[26];
memset(freq, 0, sizeof(freq));
// Iterate over characters of the string A
for (int i = 0; i < A.size(); i++) {
// Update frequency of character A[i]
freq[A[i] - 'a'] += 1;
}
// Iterate over characters of the string B
for (int i = 0; i < B.size(); i++) {
// Update frequency of character B[i]
freq[B[i] - 'a'] += 1;
}
// Store the count of all pairs
// of similar characters
int cnt = 0;
// Traverse the array freq[]
for (int i = 0; i < 26; i++) {
// Update cnt
cnt += freq[i] / 2;
}
// Print the minimum of cnt, N and M
cout << min(cnt, min(N, M));
}
// Driver Code
int main()
{
// Given strings
string A = "abdeff";
string B = "abbet";
lcsBySwapping(A, B);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the length of LCS
// possible by swapping any character
// of a string with that of another string
static void lcsBySwapping(String A, String B)
{
// Store the size of the strings
int N = A.length();
int M = B.length();
// Stores frequency of characters
int freq[] = new int[26];
// Iterate over characters of the string A
for(int i = 0; i < N; i++)
{
// Update frequency of character A[i]
freq[A.charAt(i) - 'a'] += 1;
}
// Iterate over characters of the string B
for(int i = 0; i < M; i++)
{
// Update frequency of character B[i]
freq[B.charAt(i) - 'a'] += 1;
}
// Store the count of all pairs
// of similar characters
int cnt = 0;
// Traverse the array freq[]
for(int i = 0; i < 26; i++)
{
// Update cnt
cnt += freq[i] / 2;
}
// Print the minimum of cnt, N and M
System.out.println(Math.min(cnt, Math.min(N, M)));
}
// Driver Code
public static void main(String[] args)
{
// Given strings
String A = "abdeff";
String B = "abbet";
lcsBySwapping(A, B);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to find the length of LCS
# possible by swapping any character
# of a with that of another string
def lcsBySwapping(A, B):
# Store the size of the strings
N = len(A)
M = len(B)
# Stores frequency of characters
freq = [0] * 26
# Iterate over characters of the A
for i in range(len(A)):
# Update frequency of character A[i]
freq[ord(A[i]) - ord('a')] += 1
# Iterate over characters of the B
for i in range(len(B)):
# Update frequency of character B[i]
freq[ord(B[i]) - ord('a')] += 1
# Store the count of all pairs
# of similar characters
cnt = 0
# Traverse the array freq[]
for i in range(26):
# Update cnt
cnt += freq[i] // 2
# Print the minimum of cnt, N and M
print (min(cnt, min(N, M)))
# Driver Code
if __name__ == '__main__':
# Given strings
A = "abdeff"
B = "abbet"
lcsBySwapping(A, B)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of LCS
// possible by swapping any character
// of a string with that of another string
static void lcsBySwapping(string A, string B)
{
// Store the size of the strings
int N = A.Length;
int M = B.Length;
// Stores frequency of characters
int[] freq = new int[26];
// Iterate over characters of the string A
for(int i = 0; i < N; i++)
{
// Update frequency of character A[i]
freq[A[i] - 'a'] += 1;
}
// Iterate over characters of the string B
for(int i = 0; i < M; i++)
{
// Update frequency of character B[i]
freq[B[i] - 'a'] += 1;
}
// Store the count of all pairs
// of similar characters
int cnt = 0;
// Traverse the array freq[]
for(int i = 0; i < 26; i++)
{
// Update cnt
cnt += freq[i] / 2;
}
// Print the minimum of cnt, N and M
Console.WriteLine(Math.Min(cnt, Math.Min(N, M)));
}
// Driver Code
public static void Main(string[] args)
{
// Given strings
string A = "abdeff";
string B = "abbet";
lcsBySwapping(A, B);
}
}
// This code is contributed by ukasp
Javascript
<script>
//Javascript program for the above approach
// Function to find the length of LCS
// possible by swapping any character
// of a string with that of another string
function lcsBySwapping(A, B)
{
// Store the size of the strings
var N = A.length;
var M = B.length;
// Stores frequency of characters
var freq = new Array(26);
freq.fill(0);
// Iterate over characters of the string A
for (var i = 0; i < A.length; i++) {
// Update frequency of character A[i]
freq[A[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
// Iterate over characters of the string B
for (var i = 0; i < B.length; i++) {
// Update frequency of character B[i]
freq[B[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
// Store the count of all pairs
// of similar characters
var cnt = 0;
// Traverse the array freq[]
for (var i = 0; i < 26; i++) {
// Update cnt
cnt += parseInt(freq[i] / 2);
}
// Print the minimum of cnt, N and M
document.write( Math.min(cnt, Math.min(N, M)));
}
var A = "abdeff";
var B = "abbet";
lcsBySwapping(A, B);
//This code is contributed by SoumikMondal
</script>
4
Complejidad temporal: O(N + M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA