Longest Common Substring with max XOR
Given two strings s1 and s2, the task is to find the length of the longest common substring of s1 and s2 such that the XOR is maximum.
Examples:
Input: s1 = “79567”, s2 = “56779”
Output: 2
Explanation: The longest common substring with a max XOR is “79”, which has an XOR of 14 and a length is 2.Input: s1 = “123456”, s2 = “8762347”
Output: 3
Explanation: The longest common substring with a max XOR is “234”, which has an XOR of 5 and a length is 3.
Approach: This can be solved with the following idea:
This approach uses the fact that two binary numbers have the same XOR value if and only if their bitwise XOR operation is a power of 2. Therefore, we generate all possible substrings of s1 and store their hash values in a set. Then we generate all possible substrings of s2 and check if their hash values are present in the set. If the hash value is present in the set, we update the maximum XOR value to the length of the substring.
Steps of the above approach:
- Initialize the maximum XOR value to 0 and create an empty unordered set.
- Iterate over all possible lengths of substrings starting from length 1 up to the length of s1.
- For each substring length, generate all possible substrings of that length in s1.
- For each substring generated, calculate its hash value by treating the substring as a binary number and adding it to the hash value using bitwise left shift and bitwise OR operations.
- Store the hash value in the unordered set.
- Generate all possible substrings of length len in s2.
- For each substring generated, calculate its hash value using the same method as step 4.
- Check if the hash value is present in the unordered set.
- If the hash value is present, update the maximum XOR value to the length of the substring.
- Repeat steps 2-9 for all possible substring lengths.
- Return the final value of max_xor as the length of the longest common substring of s1 and s2 with maximum XOR.
Below is the implementation of the above approach:
C++
// C++ code of the above approach #include <bits/stdc++.h> using namespace std; // Function to find length of longest // common substring whose XOR is maximum int max_xor_common_substring(string s1, string s2) { int n1 = s1.length(), n2 = s2.length(); int max_xor = 0; // Declaring Unordered_set unordered_set< int > s; for ( int len = 1; len <= n1; len++) { s.clear(); int hash_val = 0; // Start Iterating for ( int i = 0; i < len; i++) { hash_val = (hash_val << 1) + (s1[i] - '0' ); } s.insert(hash_val); for ( int i = len; i < n1; i++) { hash_val = ((hash_val << 1) + (s1[i] - '0' )) & ((1 << len) - 1); s.insert(hash_val); } hash_val = 0; for ( int i = 0; i < len; i++) { hash_val = (hash_val << 1) + (s2[i] - '0' ); } if (s.count(hash_val)) { max_xor = len; } for ( int i = len; i < n2; i++) { hash_val = ((hash_val << 1) + (s2[i] - '0' )) & ((1 << len) - 1); if (s.count(hash_val)) { max_xor = len; } } } return max_xor; } // Driver code int main() { string s1 = "79567" ; string s2 = "56779" ; // Function call int max_xor = max_xor_common_substring(s1, s2); cout << max_xor << endl; s1 = "123456" ; s2 = "8762347" ; // Function call max_xor = max_xor_common_substring(s1, s2); cout << max_xor << endl; // Output: 3 return 0; } |
Java
// Java code of the above approach import java.util.HashSet; public class MaxXORCommonSubstring { // Function to find length of longest // common substring whose XOR is maximum public static int max_xor_common_substring(String s1, String s2) { int n1 = s1.length(), n2 = s2.length(); int max_xor = 0 ; // Declaring HashSet HashSet<Integer> set = new HashSet<>(); for ( int len = 1 ; len <= n1; len++) { set.clear(); int hash_val = 0 ; // Start iterating for ( int i = 0 ; i < len; i++) { hash_val = (hash_val << 1 ) + (s1.charAt(i) - '0' ); } set.add(hash_val); for ( int i = len; i < n1; i++) { hash_val = ((hash_val << 1 ) + (s1.charAt(i) - '0' )) & (( 1 << len) - 1 ); set.add(hash_val); } hash_val = 0 ; for ( int i = 0 ; i < len; i++) { hash_val = (hash_val << 1 ) + (s2.charAt(i) - '0' ); } if (set.contains(hash_val)) { max_xor = len; } for ( int i = len; i < n2; i++) { hash_val = ((hash_val << 1 ) + (s2.charAt(i) - '0' )) & (( 1 << len) - 1 ); if (set.contains(hash_val)) { max_xor = len; } } } return max_xor; } // Driver code public static void main(String[] args) { String s1 = "79567" ; String s2 = "56779" ; // Function call int max_xor = max_xor_common_substring(s1, s2); System.out.println(max_xor); s1 = "123456" ; s2 = "8762347" ; // Function call max_xor = max_xor_common_substring(s1, s2); System.out.println(max_xor); // Output: 3 } } // This code is contributed by Vaibhav Nandan |
Python3
# Python code for the above approach # Function to find length of longest # common substring whose XOR is maximum def max_xor_common_substring(s1: str , s2: str ) - > int : n1 = len (s1) n2 = len (s2) max_xor = 0 # Declaring Set s = set () for length in range ( 1 , n1 + 1 ): s.clear() hash_val = 0 # Start Iterating for i in range (length): hash_val = (hash_val << 1 ) + ( ord (s1[i]) - ord ( '0' )) s.add(hash_val) for i in range (length, n1): hash_val = ((hash_val << 1 ) + ( ord (s1[i]) - ord ( '0' ))) & (( 1 << length) - 1 ) s.add(hash_val) hash_val = 0 for i in range (length): hash_val = (hash_val << 1 ) + ( ord (s2[i]) - ord ( '0' )) if hash_val in s: max_xor = length for i in range (length, n2): hash_val = ((hash_val << 1 ) + ( ord (s2[i]) - ord ( '0' ))) & (( 1 << length) - 1 ) if hash_val in s: max_xor = length return max_xor # Driver code if __name__ = = "__main__" : s1 = "79567" s2 = "56779" # Function call max_xor = max_xor_common_substring(s1, s2) print (max_xor) s1 = "123456" s2 = "8762347" # Function call max_xor = max_xor_common_substring(s1, s2) print (max_xor) # Output: 3 |
C#
// Include namespace system using System; using System.Collections.Generic; public class MaxXORCommonSubstring { public static int max_xor_common_substring( string s1, string s2) { var n1 = s1.Length; var n2 = s2.Length; var max_xor = 0; var set = new HashSet< int >(); for ( int len = 1; len <= n1; len++) { set .Clear(); var hash_val = 0; for ( int i = 0; i < len; i++) { hash_val = (hash_val << 1) + (( int )(s1[i]) - ( int )( '0' )); } set .Add(hash_val); for ( int i = len; i < n1; i++) { hash_val = ((hash_val << 1) + (( int )(s1[i]) - ( int )( '0' ))) & ((1 << len) - 1); set .Add(hash_val); } hash_val = 0; for ( int i = 0; i < len; i++) { hash_val = (hash_val << 1) + (( int )(s2[i]) - ( int )( '0' )); } if ( set .Contains(hash_val)) { max_xor = len; } for ( int i = len; i < n2; i++) { hash_val = ((hash_val << 1) + (( int )(s2[i]) - ( int )( '0' ))) & ((1 << len) - 1); if ( set .Contains(hash_val)) { max_xor = len; } } } return max_xor; } public static void Main( string [] args) { var s1 = "79567" ; var s2 = "56779" ; var max_xor = MaxXORCommonSubstring .max_xor_common_substring(s1, s2); Console.WriteLine(max_xor); s1 = "123456" ; s2 = "8762347" ; max_xor = MaxXORCommonSubstring .max_xor_common_substring(s1, s2); Console.WriteLine(max_xor); } } |
Javascript
// Function to find length of longest // common substring whose XOR is maximum function max_xor_common_substring(s1, s2) { let n1 = s1.length, n2 = s2.length; let max_xor = 0; // Declaring Set let s = new Set(); for (let len = 1; len <= n1; len++) { s.clear(); let hash_val = 0; // Start Iterating for (let i = 0; i < len; i++) { hash_val = (hash_val << 1) + (parseInt(s1[i]) - 0); } s.add(hash_val); for (let i = len; i < n1; i++) { hash_val = ((hash_val << 1) + (parseInt(s1[i]) - 0)) & ((1 << len) - 1); s.add(hash_val); } hash_val = 0; for (let i = 0; i < len; i++) { hash_val = (hash_val << 1) + (parseInt(s2[i]) - 0); } if (s.has(hash_val)) { max_xor = len; } for (let i = len; i < n2; i++) { hash_val = ((hash_val << 1) + (parseInt(s2[i]) - 0)) & ((1 << len) - 1); if (s.has(hash_val)) { max_xor = len; } } } return max_xor; } // Driver code let s1 = "79567" ; let s2 = "56779" ; // Function call let max_xor = max_xor_common_substring(s1, s2); console.log(max_xor); s1 = "123456" ; s2 = "8762347" ; // Function call max_xor = max_xor_common_substring(s1, s2); console.log(max_xor); |
2 3
Time Complexity: O(n^3 * log n)
Auxiliary Space: O(n^2)