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 notbool 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 stringint 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 Codeint 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 approachpublic 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 approachSIZE = 26# Function to check if two arrays# are identical or notdef 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 stringdef 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 Codeif __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 approachusing 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 approachlet SIZE = 26; // Function to check if two arrays// are identical or notfunction 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 stringfunction 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 codelet str1 = "abaabcdezzwer";let str2 = "caaabbttyh";let N = str1.length;let M = str2.length;// Function CalllongCommomPrefixAnagram(str1, str2, N, M);// This code is contributed by rameshtravel07</script> |
Output:
6
Time Complexity: O(N*26)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
