PROBLEM LINK:
Author: Yogesh Raisinghani
Tester: Yogesh Raisinghani
Editorialist: Yogesh Raisinghani
DIFFICULTY:
Easy-Medium.
PREREQUISITES:
Maths (Hashing or Bitmasking would be an advantage)
PROBLEM:
There are N strings given and each will contain digits only from 1,2,3,4 and 5.
You are supposed to find the number of strings that contains all the 5 digits after concatenating any two strings.
Quick Overview:
We need to find a number of strings that contain all the digits from 1 to 5 after concatenating any 2 strings.
One way to do directly what the question says and concatenate any two strings for all combinations and checking if they contain all digits.
But this will give TLE as the time complexity would be O(n^2) as it would require nested for loop to try every combination.
Explanation:
There are two methods to Implement this question. One is using Hashing and the other is using BitMasking.
Firstly we can say that there will be only 32(2^5) unique strings after removing duplicates i.e 1222 =12 and the order doesn’t matter here.
Now let’s try solving some example to get the logic/approach:
Given strings 12, 12, 345
Combinations possible - 1212, 12345, 12345 we got 2 required strings.
Given Strings 12, 12, 345, 345
Combinations possible - 1212, 12345, 12345, 12345, 12345, 345345 we got 4 required strings.
You can observe in the second example 1st 12 can combine with 1st 345 and produce a required string then the first 12 with the second 345 and so on…
similarly as only 32 combinations are possible and the rest will be repetitions only we only need to concentrate on those 32 strings and their counts.
First of all we need to input all strings and then remove all duplicate digits and sort them.
Then we need to keep count of all the possible 32 strings. the strings would be (1, 12, 13, 14, 15, 123, 124, 125, 133, 134, 135…and so on…).
After maintaining the counts we then just need to combine all these string counts and check whether the form required string.
For eg. in the above example :
count of 12 - 2
count of 345 -1
Then we just need to multiply the counts and ans = 2.
count of 12 - 2
count of 345 - 2
Then we just need to multiply the counts and ans = 4.
Just be careful you don’t multiply twice…if you do then divide the result by 2(this can happen in implementing).
But then there will be one corner case… if the given string contains all the 5 digits 12345.
Eg. given strings 12, 12 345, 12345
Combinations = 1212, 12345, 12345, 1212345, 1212345, 34512345 and after removing repeating digits 12, 12345, 12345, 12345, 12345, 12345
As you can see the last string produced the required string with all the strings it was concatenated… so we need to remove those.
That’s the main approach for hashing and for bit masking also it is pretty much the same way.
To understand bitmasking implement you can refer to below links.
JAIN PROBLEM
GFG
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
void uniqe(string& s)
{
set<char> uni(s.begin(), s.end());
string result(uni.begin(), uni.end());
s = result;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
map<string, long long> pos;
pos[("1")] = 0;
pos[("2")] = 0;
pos[("3")] = 0;
pos[("4")] = 0;
pos[("5")] = 0;
pos[("12")] = 0;
pos[("13")] = 0;
pos[("14")] = 0;
pos[("15")] = 0;
pos[("23")] = 0;
pos[("24")] = 0;
pos[("25")] = 0;
pos[("34")] = 0;
pos[("35")] = 0;
pos[("45")] = 0;
pos[("123")] = 0;
pos[("124")] = 0;
pos[("125")] = 0;
pos[("134")] = 0;
pos[("135")] = 0;
pos[("145")] = 0;
pos[("234")] = 0;
pos[("235")] = 0;
pos[("245")] = 0;
pos[("345")] = 0;
pos[("1234")] = 0;
pos[("1235")] = 0;
pos[("1345")] = 0;
pos[("2345")] = 0;
pos[("1245")] = 0;
pos[("12345")] = 0;
int n, ans = 0;
cin >> n;
string s[n];
for (int i = 0; i < n; i++) {
cin >> s[i];
sort(s[i].begin(), s[i].end());
uniqe(s[i]);
auto e = pos.find(s[i]);
(e->second)++;
}
for (auto i : pos) {
for (auto j : pos) {
string st = i.first + j.first;
uniqe(st);
if (st == "12345")
ans += i.second * j.second;
}
}
auto itr = pos.find("12345");
cout << (ans - (itr->second)) / 2 << endl;
}
}