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 moduloconst long long MAX_SIZE = 1000001;const long long ALPHABET_SIZE = 11;const long long MODULO = 1110111110111;// Array to store base valuesint base[MAX_SIZE];// Function to calculate hash value of a stringint 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 problemvoid 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 functionint 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;} |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
