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

1

Problem - A - Codeforces can anyone please send the solution of this queston in c++ !

2
  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
3

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

2 Likes
4
5

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
6

thanks :slight_smile: i got it