 # http://codeforces.com/contest/1278/problem/A

http://codeforces.com/contest/1278/problem/A can anyone please send the solution of this queston in c++ !

1. Store the character count of all the characters of p in a map.
2. traverse the h string, and if you find a character of h in map then
do -
a. create the copy of the original map (clone).
b. take loop from that point to p.length() and check if all the characters you
traverse are present in the copy map and decrease the count of that
character. If the character count gets 0, remove the character from
copymap.
c. if the copy map is empty by the end of inner loop, print yes. else repeat until
the length of h
3. If you don’t get the result after the entire loop print no.

Hope I was clear.
I have the code in java, if you want I can share

2 Likes

Sort p, for every substring (s) of length |p| in h, if p==sorted(s) then Yes. Else No.

2 Likes

Just check out the code, Hope, it’s would be easy to you:

``````#define sz(a) a.size()
#define all(a) a.begin(), a.end()

string s, h, S;
cin >> s >> h;
int n = sz(s), nn = sz(h);
if (n > nn) return cout << "NO\n", 0;
sort(all(s));
for (register int i = 0; i <= nn - n; i++) {
S = h.substr(i, n);
sort(all(S));
if (s == S) return cout << "YES\n", 0;
}
return cout << "NO\n", 0;
``````

If you want to ignore sorting, then you need to use hash_map, BUT that’s difficult to to debug:

Hash_map Code
``````  string s, h;
cin >> s >> h;
int n = sz(s), nn = sz(h), cnt = 0;
if (n > nn) return cout << "NO\n", 0;
unordered_map<char, int> mp, chk;
for (auto ch : s) mp[ch]++;
int m = sz(mp);

char ch;
for (register int i = 0; i < n; i++) {
ch = h[i];
if (mp[ch]) {
if (mp[ch] == chk[ch]) {
cnt--;
}
chk[ch]++;
if (mp[ch] == chk[ch]) {
cnt++;
}
}
}
if (cnt == m) {
return cout << "YES\n", 0;
}

for (register int i = n; i < nn; i++) {
ch = h[i];
char c = h[i - n];
if (mp[c]) {
if (mp[c] == chk[c]) {
cnt--;
}
if (mp[c] + 1 == chk[c]) {
cnt++;
}
chk[c]--;
}
if (mp[ch]) {
if (mp[ch] == chk[ch]) {
cnt--;
}
chk[ch]++;
if (mp[ch] == chk[ch]) {
cnt++;
}
}
if (cnt == m) {
return cout << "YES\n", 0;
}
}

return cout << "NO\n", 0;
``````
1 Like

thanks i got it