1. Python
  2. Find the longest common prefix between two strings after performing permutations on the second string

Find the longest common prefix between two strings after performing permutations on the second string



Examples : 

  Input : a = "here", b = "there"  Output : 4 The 2nd string can be made "heret" by just swapping characters and thus the longest prefix is ​​of length 4.  Input : a = "you", b = "me"  Output  : 0

Considering that we are only allowed to perform permutations in the line and the prefix length should be maximum. So the idea is to go through the line and check if the frequency of the current character in the line the same or less than the line , If yes, then move forward to line otherwise break and print the length of the part of line a to which the character in line ,

Below is the implementation of the above approach:

C ++

// C ++ program for finding the longest
// common prefix between two lines
// after swapping on the second line
# include & lt; bits / stdc ++. h & gt;

using namespace std;

 

 

void LengthLCP (string x, string y)

{

 

 

int fr [26] = {0};

 

int a = x.length (); // length х

int b = y.length (); // length for

 

for ( int i = 0; i & lt; b; i ++)

{

// create a frequency array

// characters at

fr [y [i] - 97] + = 1;

}

// keep the length

  // longest common prefix

int c = 0;

 

for ( int i = 0; i & lt; a ; i ++)

{

// check character frequency for

// position i in x in b is greater than zero or not

// if zero, we increase the number of prefixes by 1

if (fr [x [i] - 97] & gt; 0) {

c + = 1;

fr [x [i] - 97] - = 1;

}

else

  break ;

}

cout & lt; & lt; (c) & lt; & lt; endl;

}
// Driver code

int main ()

{

string x = "here" , y =  "there" ;

 
LengthLCP (x, y);

 

return 0;

}
// provided by Arnab Kundu

Java

// Java program for finding the longest
// common prefix between the two lines
// after swapping on the second line

 

public class GFG {

 

static void LengthLCP (String x, String y)

{

 

 

int fr [] = new int [ 26 ];

 

int a = x.length (); // length x

int b = y.length (); // length for

 

for ( int i = 0 ; i & lt; b; i ++)

{

// create a frequency array

// symbols for

fr [y.charAt (i) - 97 ] + = 1 ;

}

// keep the length

  // longest common prefix

int c = 0 ;

 

for ( int i = 0 ; i & lt; a; i ++)

{

// check character frequency for

// position i in x in b is greater than zero or not

// if zero, we increase the number of prefixes by 1

if (fr [x.charAt (i) - 97 ] & gt; 0 ) {

  c + = 1 ;

fr [x.charAt (i) - 97 ] - = 1 ;

}

else

  break ;

}

System.out.println ((c));

}

 

  

  public static void main (String args [] )

{

  String x = " here " , y =  "there" ;

 

LengthLCP (x, y);

 

 

}

// This code is provided by ANKITRAI1

}

  

python3

# Python program to find the longest
# common prefix between two lines
# after swapping on the second line

 

def LengthLCP (x, y):

fr = [ 0 ] * 26

 

a = len (x) # length x

b = len (y) # length at

 

  for i in range (b):

# create a frequency array

  # of y characters

  fr [ ord (y [i]) - 97 ] + = 1

 

  # length storage

# the most long common prefix

c = 0  

 

for i in range ( a):

# check character frequency for

# position i in x in b is greater than zero or not

# if zero, we increase the number of prefixes by 1

  if (fr [ ord (x [i]) - 97 ] & gt; 0 ):

  c + = 1

fr [ ord (x [i]) - 97 ] - = 1

else :

break

print (c)

  
Driver code

 

x, y = "here" , " there "

  
LengthLCP (x, y)

C #

PHP

// C # program for finding the longest
// common prefix between two lines
// after swaps to
// second line

using System;

 

class GFG 

{ 

  

static void LengthLCP (String x, String y) 

{ 

int [] fr = new int [26]; 

 

int a = x.Length; // length x

int b = y.Length; // length for

 

for ( int i = 0; i & lt; b; i ++) 

{ 

// create a frequency array

// y characters

fr [y [i] - 97] + = 1; 

} 

 

  // keep the length

// longest common prefix

  int c = 0; 

 

for ( int i = 0; i & lt; a; i ++) 

{ 

// check frequency

// character at position i

  // xcb greater than zero

// or not, if zero, we increase

// number of prefixes by 1

if (fr [x [i] - 97] & gt; 0)

  { 

c + = 1; 

fr [x [i] - 97] - = 1; 

} 

else

  break ; 

} 

Console.Write ((c)); 

} 

 
// Driver code

public static void Main () 

{ 

String x = "here" , y = " there " ; 

 

LengthLCP (x, y); 

} 
} 

 
// This code is provided by 29AjayKumar

& lt;? Php 
/ / PHP program to find the longest
// common prefix between two lines
// after execution permutations on the second line

 

function LengthLCP ( $ x , $ y )

{

 

  

$ fr = array_fill (0,26, NULL);

 

$ a = strlen ( $ x ); // length x

$ b = strlen ( $ y ); // length for

 

for ( $ i = 0; $ i & lt; $ b ; $ i ++)

{

// create a frequency array

// symbols y

$ fr [ord ( $ y [ $ i ]) - 97] + = 1;

}

 

  // keep the length

// longest common prefix

  $ c = 0;

 

for ( $ i = 0; $ i & lt; $ a ; $ i ++)

{

// check the character frequency for

// position i in x in b is greater than zero or not

// if zero, we increase the number of prefixes by 1

if ( $ fr [ord ( $ x [ $ i ]) - 97] & gt; 0)

{

$ c + = 1;

$ fr [ord ( $ x [ $ i ]) - 97] - = 1;

}

else

  break ;

}

echo $ c ;

}

 
// Driver code

$ x = "here" ;

$ y = "there" ;

 

LengthLCP ( $ x , $ y );

 

return 0;

 
// This code is provided by ChitraNayal
? & gt;

Exit: 

 4

}

else

  break ;

}

echo $ c ;

}

 
// Driver code

$ x = "here" ;

$ y = "there" ;

 

LengthLCP ( $ x , $ y );

 

return 0;

 
// This code is provided by ChitraNayal
? & gt;

Exit: 

 4

}

else

  break ;

}

echo $ c ;

}

 
// Driver code

$ x = "here" ;

$ y = "there" ;

 

LengthLCP ( $ x , $ y );