Longest Common Subsequence ( LCS ) by repeatedly swapping characters of a string with characters of another string | C ++ 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 ; Store the size of the strings ; Stores frequency of characters ; Iterate over characters of the string A ; Update frequency of character A [ i ] ; Iterate over characters of the string B ; Update frequency of character B [ i ] ; Store the count of all pairs of similar characters ; Traverse the array freq [ ] ; Update cnt ; Print the minimum of cnt , N and M ; Driver Code ; Given strings
#include <bits/stdc++.h> NEW_LINE using namespace std ; void lcsBySwapping ( string A , string B ) { int N = A . size ( ) ; int M = B . size ( ) ; int freq [ 26 ] ; memset ( freq , 0 , sizeof ( freq ) ) ; for ( int i = 0 ; i < A . size ( ) ; i ++ ) { freq [ A [ i ] - ' a ' ] += 1 ; } for ( int i = 0 ; i < B . size ( ) ; i ++ ) { freq [ B [ i ] - ' a ' ] += 1 ; } int cnt = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { cnt += freq [ i ] / 2 ; } cout << min ( cnt , min ( N , M ) ) ; } int main ( ) { string A = " abdeff " ; string B = " abbet " ; lcsBySwapping ( A , B ) ; return 0 ; }