Dadas dos strings y . Encuentre el prefijo común más largo entre ellos después de realizar cero o más operaciones en la string . En cada operación, puede intercambiar dos letras cualesquiera.
Ejemplos :
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
Dado que solo podemos realizar intercambios en la string y la longitud del prefijo debe maximizarse. Entonces, la idea es atravesar la string y verificar si la frecuencia del carácter actual en la string es igual o menor que la de la string . En caso afirmativo, avance en la string y, de lo contrario, rompa e imprima la longitud de la parte de la string hasta la que coincide un carácter en la string .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the longest // common prefix between two strings // after performing swaps on the second string #include <bits/stdc++.h> using namespace std; void LengthLCP(string x, string y) { int fr[26]={0}; int a = x.length(); // length of x int b = y.length(); // length of y for (int i=0 ;i<b ; i++) { // creating frequency array of // characters of y fr[y[i] - 97] += 1; } // storing the length of // longest common prefix int c = 0; for (int i=0 ;i<a ; i++) { // checking if the frequency of the character at // position i in x in b is greater than zero or not // if zero we increase the prefix count by 1 if (fr[x[i] - 97] > 0){ c += 1; fr[x[i] - 97] -= 1; } else break; } cout<<(c)<<endl; } // Driver Code int main() { string x="here", y = "there"; LengthLCP(x, y); return 0; } //contributed by Arnab Kundu
Java
// Java program to find the longest // common prefix between two strings // after performing swaps on the second string public class GFG { static void LengthLCP(String x, String y) { int fr[]=new int [26]; int a = x.length(); // length of x int b = y.length(); // length of y for (int i=0 ;i<b ; i++) { // creating frequency array of // characters of y fr[y.charAt(i) - 97] += 1; } // storing the length of // longest common prefix int c = 0; for (int i=0 ;i<a ; i++) { // checking if the frequency of the character at // position i in x in b is greater than zero or not // if zero we increase the prefix count by 1 if (fr[x.charAt(i) - 97] > 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 contributed by ANKITRAI1 }
Python3
# Python program to find the longest # common prefix between two strings # after performing swaps on the second string def LengthLCP(x, y): fr = [0] * 26 a = len(x) # length of x b = len(y) # length of y for i in range(b): # creating frequency array of # characters of y fr[ord(y[i]) - 97] += 1 # storing the length of # longest common prefix c = 0 for i in range(a): # checking if the frequency of the character at # position i in x in b is greater than zero or not # if zero we increase the prefix count by 1 if (fr[ord(x[i]) - 97] > 0): c += 1 fr[ord(x[i]) - 97] -= 1 else: break print(c) # Driver Code x, y = "here", "there" LengthLCP(x, y)
C#
// C# program to find the longest // common prefix between two strings // after performing swaps on the // second string using System; class GFG { static void LengthLCP(String x, String y) { int []fr = new int [26]; int a = x.Length; // length of x int b = y.Length; // length of y for (int i = 0 ; i < b; i++) { // creating frequency array // of characters of y fr[y[i] - 97] += 1; } // storing the length of // longest common prefix int c = 0; for (int i = 0 ; i < a; i++) { // checking if the frequency of // the character at position i // in x in b is greater than zero // or not if zero we increase the // prefix count by 1 if (fr[x[i] - 97] > 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 contributed by 29AjayKumar
PHP
<?php // PHP program to find the longest // common prefix between two strings // after performing swaps on the second string function LengthLCP($x, $y) { $fr = array_fill(0,26,NULL); $a = strlen($x); // length of x $b = strlen($y); // length of y for ($i = 0 ;$i < $b ; $i++) { // creating frequency array of // characters of y $fr[ord($y[$i]) - 97] += 1; } // storing the length of // longest common prefix $c = 0; for ($i = 0 ;$i < $a ; $i++) { // checking if the frequency of the character at // position i in x in b is greater than zero or not // if zero we increase the prefix count by 1 if ($fr[ord($x[$i]) - 97] > 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 contributed by ChitraNayal ?>
Javascript
<script> // JavaScript program to find the long // common prefix between two strings // after performing swaps on the second string function LengthLCP(x, y) { let fr = Array(26).fill(0); let a = x.length; // length of x let b = y.length; // length of y for (let i=0 ;i<b ; i++) { // creating frequency array of // characters of y fr[y[i].charCodeAt() - 97] += 1; } // storing the length of // longest common prefix let c = 0; for (let i=0 ;i<a ; i++) { // checking if the // frequency of the character at // position i in x in b is greater // than zero or not // if zero we increase the // prefix count by 1 if (fr[x[i].charCodeAt() - 97] > 0){ c += 1; fr[x[i].charCodeAt() - 97] -= 1; } else break; } document.write((c)) ; } // driver code let x="here", y = "there"; LengthLCP(x, y); </script>
Producción:
4