Longest Common Subsequence ( LCS ) by repeatedly swapping characters of a string with characters of another string | Java 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void lcsBySwapping ( String A , String B ) { int N = A . length ( ) ; int M = B . length ( ) ; int freq [ ] = new int [ 26 ] ; for ( int i = 0 ; i < N ; i ++ ) { freq [ A . charAt ( i ) - ' a ' ] += 1 ; } for ( int i = 0 ; i < M ; i ++ ) { freq [ B . charAt ( i ) - ' a ' ] += 1 ; } int cnt = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { cnt += freq [ i ] / 2 ; } System . out . println ( Math . min ( cnt , Math . min ( N , M ) ) ) ; } public static void main ( String [ ] args ) { String A = " abdeff " ; String B = " abbet " ; lcsBySwapping ( A , B ) ; } }