Find string with a single differing position in the given n strings
Given n strings and q queries, for each query, a string array s[] is provided. The task is to determine, for each query, whether there exists a string among the n given strings that differs from s[] in exactly one position.
Note: Each string consists only of letters ‘a’, ‘b’, ‘c’.
Example:
Input: n = 2, q = 3, s[] = {“aaaaa”, “acacaca”}, queries[] = {“aabaa”, “ccacacc”, “caaac”}
Output:
YES
NO
NOInput: n = 1, q = 5, s[] = {“acbacbacb”}, queries[] = {“cbacbacb”, “acbacbac”, “aacbacbacb”, “acbacbacbb”, “acbaabacb”}
Output:
NO
NO
NO
NO
YES
Approach:
The idea is to use a hash function to convert each string into a unique integer (hash value), which is then stored in a set for quick lookup. The hash function used here is a simple polynomial rolling hash function, where each character of the string is multiplied by a base raised to the power of its position in the string, and these products are then added together modulo a large prime number.
When a query string is received, then calculates its hash value and then checks if there exists a hash value in the set that can be obtained by changing exactly one character in the query string. This is done by iterating over each character in the query string, changing it to ‘a’, ‘b’, or ‘c’ (if it’s not already that character), recalculating the hash value, and checking if this new hash value exists in the set.
If such a hash value is found, it means there exists a string in the original set that differs from the query string in exactly one position, and the program prints “YES”. If no such hash value is found after checking all characters, the program prints “NO”.
Steps-by-step:
- Initialize an empty set stringSet to store hash values of strings.
- Insert hash values of each string into the set.
- Iterate through each query:
- Compute the hash value of the query.
- Check if there exists a string in the set that differs in exactly one position from the query.
- Print “YES” or “NO” based on the existence.
Below is the implementation of the above approach:
C++
#include <iostream> #include <set> #include <string> using namespace std; // Constants for maximum size, alphabet size and modulo const long long MAX_SIZE = 1000001; const long long ALPHABET_SIZE = 11; const long long MODULO = 1110111110111; // Array to store base values int base[MAX_SIZE]; // Function to calculate hash value of a string int calculateHash(string& s) { int hashValue = 0; // Loop through each character in the string for ( int i = 0; i < s.size(); i++) { // Calculate the hash value hashValue += s[i] * base[i]; hashValue %= MODULO; } return hashValue; } // Function to solve the problem void solve(string s[], int numStrings, const string queries[], int q) { set< int > stringSet; // Insert hash values of s into the set for ( int i = 0; i < numStrings; i++) { stringSet.insert(calculateHash(s[i])); } // Process each query for ( int i = 0; i < q; i++) { string query = queries[i]; int hashValue = calculateHash(query); bool exists = false ; // Check if there exists a string that differs from // the query in exactly one position for ( int j = 0; j < query.size(); j++) { for ( char c = 'a' ; c < 'd' ; c++) { if (c != query[j]) { exists |= (stringSet.count( (hashValue + (c - query[j]) * base[j] + 4 * MODULO) % MODULO)); } } } // Print the result cout << (exists ? "YES" : "NO" ) << endl; } } // Main function int main() { // Initialize base array base[0] = 1; for ( int i = 1; i < MAX_SIZE; i++) { base[i] = base[i - 1] * ALPHABET_SIZE % MODULO; } // Static input: string s[] = { "acbacbacb" }; int numStrings = sizeof (s) / sizeof (s[0]); string queries[] = { "cbacbacb" , "acbacbac" , "aacbacbacb" , "acbacbacbb" , "acbaabacb" }; int q = sizeof (queries) / sizeof (queries[0]); // Call the solve function solve(s, numStrings, queries, q); return 0; } |
Java
// Java code for the above approach import java.util.HashSet; import java.util.Set; class GFG { // Constants for maximum size, alphabet size, and modulo static final long MAX_SIZE = 1000001 ; static final long ALPHABET_SIZE = 11 ; static final long MODULO = 1110111110111L; // Array to store base values static long [] base = new long [( int )MAX_SIZE]; // Function to calculate hash value of a string static long calculateHash(String s) { long hashValue = 0 ; // Loop through each character in the string for ( int i = 0 ; i < s.length(); i++) { // Calculate the hash value hashValue += s.charAt(i) * base[i]; hashValue %= MODULO; } return hashValue; } // Function to solve the problem static void solve(String[] s, int numStrings, String[] queries, int q) { Set<Long> stringSet = new HashSet<>(); // Insert hash values of s into the set for ( int i = 0 ; i < numStrings; i++) { stringSet.add(calculateHash(s[i])); } // Process each query for ( int i = 0 ; i < q; i++) { String query = queries[i]; long hashValue = calculateHash(query); boolean exists = false ; // Check if there exists a string that differs // from the query in exactly one position for ( int j = 0 ; j < query.length(); j++) { for ( char c = 'a' ; c < 'd' ; c++) { if (c != query.charAt(j)) { exists |= stringSet.contains( (hashValue + (c - query.charAt(j)) * base[j] + 4 * MODULO) % MODULO); } } } // Print the result System.out.println(exists ? "YES" : "NO" ); } } // Main function public static void main(String[] args) { // Initialize base array base[ 0 ] = 1 ; for ( int i = 1 ; i < MAX_SIZE; i++) { base[i] = (base[i - 1 ] * ALPHABET_SIZE) % MODULO; } // Static input String[] s = { "acbacbacb" }; int numStrings = s.length; String[] queries = { "cbacbacb" , "acbacbac" , "aacbacbacb" , "acbacbacbb" , "acbaabacb" }; int q = queries.length; // Call the solve function solve(s, numStrings, queries, q); } } // This code is contributed by ragul21 |
Python3
# Constants for maximum size, alphabet size, and modulo MAX_SIZE = 1000001 ALPHABET_SIZE = 11 MODULO = 1110111110111 # Array to store base values base = [ 0 ] * MAX_SIZE # Function to calculate hash value of a string def calculate_hash(s): hash_value = 0 # Loop through each character in the string for i in range ( len (s)): # Calculate the hash value hash_value + = ord (s[i]) * base[i] hash_value % = MODULO return hash_value # Function to solve the problem def solve(s, num_strings, queries, q): string_set = set () # Insert hash values of s into the set for i in range (num_strings): string_set.add(calculate_hash(s[i])) # Process each query for i in range (q): query = queries[i] hash_value = calculate_hash(query) exists = False # Check if there exists a string that differs from # the query in exactly one position for j in range ( len (query)): for c in range ( ord ( 'a' ), ord ( 'd' )): if chr (c) ! = query[j]: exists | = (hash_value + (c - ord (query[j])) * base[j] + 4 * MODULO) % MODULO in string_set # Print the result print ( "YES" if exists else "NO" ) # Main function if __name__ = = "__main__" : # Initialize base array base[ 0 ] = 1 for i in range ( 1 , MAX_SIZE): base[i] = base[i - 1 ] * ALPHABET_SIZE % MODULO # Static input: s = [ "acbacbacb" ] num_strings = len (s) queries = [ "cbacbacb" , "acbacbac" , "aacbacbacb" , "acbacbacbb" , "acbaabacb" ] q = len (queries) # Call the solve function solve(s, num_strings, queries, q) |
C#
using System; using System.Collections.Generic; class Program { // Constants for maximum size, alphabet size and modulo const long MAX_SIZE = 1000001; const long ALPHABET_SIZE = 11; const long MODULO = 1110111110111; // Array to store base values static long [] baseArray = new long [MAX_SIZE]; // Function to calculate hash value of a string static long CalculateHash( string s) { long hashValue = 0; // Loop through each character in the string for ( int i = 0; i < s.Length; i++) { // Calculate the hash value hashValue += s[i] * baseArray[i]; hashValue %= MODULO; } return hashValue; } // Function to solve the problem static void Solve( string [] s, int numStrings, string [] queries, int q) { HashSet< long > stringSet = new HashSet< long >(); // Insert hash values of s into the set for ( int i = 0; i < numStrings; i++) { stringSet.Add(CalculateHash(s[i])); } // Process each query for ( int i = 0; i < q; i++) { string query = queries[i]; long hashValue = CalculateHash(query); bool exists = false ; // Check if there exists a string that differs // from the query in exactly one position for ( int j = 0; j < query.Length; j++) { for ( char c = 'a' ; c < 'd' ; c++) { if (c != query[j]) { exists |= stringSet.Contains( (hashValue + (c - query[j]) * baseArray[j] + 4 * MODULO) % MODULO); } } } // Print the result Console.WriteLine(exists ? "YES" : "NO" ); } } // Main function static void Main() { // Initialize base array baseArray[0] = 1; for ( int i = 1; i < MAX_SIZE; i++) { baseArray[i] = baseArray[i - 1] * ALPHABET_SIZE % MODULO; } // Static input: string [] s = { "acbacbacb" }; int numStrings = s.Length; string [] queries = { "cbacbacb" , "acbacbac" , "aacbacbacb" , "acbacbacbb" , "acbaabacb" }; int q = queries.Length; // Call the solve function Solve(s, numStrings, queries, q); } } |
Javascript
// JavaScript code for the above approach // Constants for maximum size, alphabet size, and modulo const MAX_SIZE = 1000001; const ALPHABET_SIZE = 11; const MODULO = 1110111110111n; // Array to store base values const base = new Array(MAX_SIZE).fill(0n); // Function to calculate hash value of a string function calculateHash(s) { let hashValue = 0n; // Loop through each character in the string for (let i = 0; i < s.length; i++) { // Calculate the hash value hashValue += BigInt(s.charCodeAt(i)) * base[i]; hashValue %= MODULO; } return hashValue; } // Function to solve the problem function solve(s, numStrings, queries, q) { const stringSet = new Set(); // Insert hash values of s into the set for (let i = 0; i < numStrings; i++) { stringSet.add(calculateHash(s[i])); } // Process each query for (let i = 0; i < q; i++) { const query = queries[i]; const hashValue = calculateHash(query); let exists = false ; // Check if there exists a string that differs // from the query in exactly one position for (let j = 0; j < query.length; j++) { for (let c = 'a' .charCodeAt(0); c < 'd' .charCodeAt(0); c++) { if (c !== query.charCodeAt(j)) { exists |= stringSet.has( (hashValue + (BigInt(c - query.charCodeAt(j))) * base[j] + 4n * MODULO) % MODULO ); } } } // Print the result console.log(exists ? "YES" : "NO" ); } } // Main function function main() { // Initialize base array base[0] = 1n; for (let i = 1; i < MAX_SIZE; i++) { base[i] = (base[i - 1] * BigInt(ALPHABET_SIZE)) % MODULO; } // Static input const s = [ "acbacbacb" ]; const numStrings = s.length; const queries = [ "cbacbacb" , "acbacbac" , "aacbacbacb" , "acbacbacbb" , "acbaabacb" ]; const q = queries.length; // Call the solve function solve(s, numStrings, queries, q); } // Call the main function main(); |
NO NO NO NO YES
Time Complexity: O(q * MAX_SIZE), where q is the number of queries and MAX_SIZE is the maximum length of a string.
Auxiliary Space: O(MAX_SIZE + n), where MAX_SIZE is the maximum length of a string and n is the number of input strings.