20-Coding-Patterns-DesignGurus.org/11_permutations_in_string.cpp

/* Problem: https://leetcode.com/problems/permutation-in-string/ */

#include <iostream>
#include <unordered_map>

bool solution(const std::string s1, const std::string s2) {
  if (s1.length() > s2.length())
    return false;
  std::size_t s1_len = s1.length();
  std::unordered_map<char, std::size_t> s1_count, s2_substr_count;
  for (const char c : s1)
    s1_count[c]++;
  for (auto c = s2.cbegin(), e = s2.cbegin() + s1.length(); c != e; c++) {
    s2_substr_count[*c]++;
  }
  for (std::size_t i = s1_len, upto = s2.length(); i < upto; i++) {
    bool match_found = true;
    for (auto const [character, count] : s1_count) {
      if (s2_substr_count[character] != count) {
        match_found = false;
        break;
      }
    }
    if (match_found)
      return true;
    s2_substr_count[s2[i - s1_len]]--;
    s2_substr_count[s2[i]]++;
  }
  for (auto const [character, count] : s1_count) {
    if (s2_substr_count[character] != count)
      return false;
  }
  return true;
}

int main() {
  std::cout << solution("ab", "eidbaooo") << '\n'
            << solution("ab", "eidboaoo") << '\n'
            << solution("dinitrophenylhydrazine", "dimethylhydrazine") << '\n';
}