Length of longest prefix anagram which are common in given two strings
Given two strings str1 and str2 of the lengths of N and M respectively, the task is to find the length of the longest anagram string that is prefix substring of both strings.
Examples:
Input: str1 = “abaabcdezzwer”, str2 = “caaabbttyh”
Output: 6
Explanation:
Prefixes of length 1 of string str1 and str2 are “a”, and “c”.
Prefixes of length 2 of string str1 and str2 are “ab”, and “ca”.
Prefixes of length 3 of string str1 and str2 are “aba”, and “caa”.
Prefixes of length 4 of string str1 and str2 are “abaa”, and “caaa”.
Prefixes of length 5 of string str1 and str2 are “abaab”, and “caaab”.
Prefixes of length 6 of string str1 and str2 are “abaabc”, and “caaabb”.
Prefixes of length 7 of string str1 and str2 are “abaabcd”, and “caaabbt”.
Prefixes of length 8 of string str1 and str2 are “abaabcde”, and “caaabbtt”.
Prefixes of length 9 of string str1 and str2 are “abaabcdez”, and “caaabbtty”.
Prefixes of length 10 of string str1 and str2 are “abaabcdezz”, and “caaabbttyh”.
Prefixes of length 6 are anagram with each other only.Input: str1 = “abcdef”, str2 = “tuvwxyz”
Output: 0
Approach: The idea is to use Hashing for solving the above problem. Follow the steps below to solve the problem:
- Initialize two integer arrays freq1[] and freq2[], each of size 26, to store the count of characters in strings str1 and str2 respectively.
- Initialize a variable, say ans, to store the result.
- Iterate over the characters of the string present in indices [0, minimum(N – 1, M – 1)] and perform the following:
- Increment count of str1[i] in freq1[] array and count of str2[i] in freq2[] array by 1.
- Check if the frequency array freq1[] is the same as the frequency array freq2[], assign ans = i + 1.
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define SIZE 26 // Function to check if two arrays // are identical or not bool longHelper( int freq1[], int freq2[]) { // Iterate over the range [0, SIZE] for ( int i = 0; i < SIZE; ++i) { // If frequency any character is // not same in both the strings if (freq1[i] != freq2[i]) { return false ; } } // Otherwise return true ; } // Function to find the maximum // length of the required string int longCommomPrefixAnagram( string s1, string s2, int n1, int n2) { // Store the count of // characters in string str1 int freq1[26] = { 0 }; // Store the count of // characters in string str2 int freq2[26] = { 0 }; // Stores the maximum length int ans = 0; // Minimum length of str1 and str2 int mini_len = min(n1, n2); for ( int i = 0; i < mini_len; ++i) { // Increment the count of // characters of str1[i] in // freq1[] by one freq1[s1[i] - 'a' ]++; // Increment the count of // characters of str2[i] in // freq2[] by one freq2[s2[i] - 'a' ]++; // Checks if prefixes are // anagram or not if (longHelper(freq1, freq2)) { ans = i + 1; } } // Finally print the ans cout << ans; } // Driver Code int main() { string str1 = "abaabcdezzwer" ; string str2 = "caaabbttyh" ; int N = str1.length(); int M = str2.length(); // Function Call longCommomPrefixAnagram(str1, str2, N, M); return 0; } |
Java
// Java program for the above approach public class Main { static int SIZE = 26 ; // Function to check if two arrays // are identical or not static boolean longHelper( int [] freq1, int [] freq2) { // Iterate over the range [0, SIZE] for ( int i = 0 ; i < SIZE; ++i) { // If frequency any character is // not same in both the strings if (freq1[i] != freq2[i]) { return false ; } } // Otherwise return true ; } // Function to find the maximum // length of the required string static void longCommomPrefixAnagram( String s1, String s2, int n1, int n2) { // Store the count of // characters in string str1 int [] freq1 = new int [ 26 ]; // Store the count of // characters in string str2 int [] freq2 = new int [ 26 ]; // Stores the maximum length int ans = 0 ; // Minimum length of str1 and str2 int mini_len = Math.min(n1, n2); for ( int i = 0 ; i < mini_len; ++i) { // Increment the count of // characters of str1[i] in // freq1[] by one freq1[s1.charAt(i) - 'a' ]++; // Increment the count of // characters of str2[i] in // freq2[] by one freq2[s2.charAt(i) - 'a' ]++; // Checks if prefixes are // anagram or not if (longHelper(freq1, freq2)) { ans = i + 1 ; } } // Finally print the ans System.out.print(ans); } // Driver code public static void main(String[] args) { String str1 = "abaabcdezzwer" ; String str2 = "caaabbttyh" ; int N = str1.length(); int M = str2.length(); // Function Call longCommomPrefixAnagram(str1, str2, N, M); } } // This code is contributed by divyeshrrabadiya07. |
Python3
# Python3 program for the above approach SIZE = 26 # Function to check if two arrays # are identical or not def longHelper(freq1, freq2): # Iterate over the range [0, SIZE] for i in range ( 26 ): # If frequency any character is # not same in both the strings if (freq1[i] ! = freq2[i]): return False # Otherwise return True # Function to find the maximum # length of the required string def longCommomPrefixAnagram(s1, s2, n1, n2): # Store the count of # characters in str1 freq1 = [ 0 ] * 26 # Store the count of # characters in str2 freq2 = [ 0 ] * 26 # Stores the maximum length ans = 0 # Minimum length of str1 and str2 mini_len = min (n1, n2) for i in range (mini_len): # Increment the count of # characters of str1[i] in # freq1[] by one freq1[ ord (s1[i]) - ord ( 'a' )] + = 1 # Increment the count of # characters of stord(r2[i]) in # freq2[] by one freq2[ ord (s2[i]) - ord ( 'a' )] + = 1 # Checks if prefixes are # anagram or not if (longHelper(freq1, freq2)): ans = i + 1 # Finally print the ans print (ans) # Driver Code if __name__ = = '__main__' : str1 = "abaabcdezzwer" str2 = "caaabbttyh" N = len (str1) M = len (str2) # Function Call longCommomPrefixAnagram(str1, str2, N, M) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { static int SIZE = 26; // Function to check if two arrays // are identical or not static bool longHelper( int [] freq1, int [] freq2) { // Iterate over the range [0, SIZE] for ( int i = 0; i < SIZE; ++i) { // If frequency any character is // not same in both the strings if (freq1[i] != freq2[i]) { return false ; } } // Otherwise return true ; } // Function to find the maximum // length of the required string static void longCommomPrefixAnagram( string s1, string s2, int n1, int n2) { // Store the count of // characters in string str1 int [] freq1 = new int [26]; // Store the count of // characters in string str2 int [] freq2 = new int [26]; // Stores the maximum length int ans = 0; // Minimum length of str1 and str2 int mini_len = Math.Min(n1, n2); for ( int i = 0; i < mini_len; ++i) { // Increment the count of // characters of str1[i] in // freq1[] by one freq1[s1[i] - 'a' ]++; // Increment the count of // characters of str2[i] in // freq2[] by one freq2[s2[i] - 'a' ]++; // Checks if prefixes are // anagram or not if (longHelper(freq1, freq2)) { ans = i + 1; } } // Finally print the ans Console.Write(ans); } // Driver code static void Main() { string str1 = "abaabcdezzwer" ; string str2 = "caaabbttyh" ; int N = str1.Length; int M = str2.Length; // Function Call longCommomPrefixAnagram(str1, str2, N, M); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach let SIZE = 26; // Function to check if two arrays // are identical or not function longHelper(freq1, freq2) { // Iterate over the range [0, SIZE] for (let i = 0; i < SIZE; ++i) { // If frequency any character is // not same in both the strings if (freq1[i] != freq2[i]) { return false ; } } // Otherwise return true ; } // Function to find the maximum // length of the required string function longCommomPrefixAnagram(s1, s2, n1, n2) { // Store the count of // characters in string str1 let freq1 = new Array(26); freq1.fill(0); // Store the count of // characters in string str2 let freq2 = new Array(26); freq2.fill(0); // Stores the maximum length let ans = 0; // Minimum length of str1 and str2 let mini_len = Math.min(n1, n2); for (let i = 0; i < mini_len; ++i) { // Increment the count of // characters of str1[i] in // freq1[] by one freq1[s1[i].charCodeAt() - 'a' .charCodeAt()]++; // Increment the count of // characters of str2[i] in // freq2[] by one freq2[s2[i].charCodeAt() - 'a' .charCodeAt()]++; // Checks if prefixes are // anagram or not if (longHelper(freq1, freq2)) { ans = i + 1; } } // Finally print the ans document.write(ans); } // Driver code let str1 = "abaabcdezzwer" ; let str2 = "caaabbttyh" ; let N = str1.length; let M = str2.length; // Function Call longCommomPrefixAnagram(str1, str2, N, M); // This code is contributed by rameshtravel07 </script> |
6
Time Complexity: O(N*26)
Auxiliary Space: O(1)