How can i optimize this Codewars c++ code?

Question

i was doing a Codewars training in c++ and my code is working good but it says that it is not fast enough to pass all the tests. In this training, i need to check if a portion of str1 characters can be rearranged to match str2 (all passed as parameters and being const). Pretty simple subject but how can i optimize it ? Here's my code :

bool scramble(const std::string& s1, const std::string& s2){
   int j = 0;
   int i = 0;
   size_t good_count = 0;
   char tmp[s1.size()];

   std::strcpy(tmp, s1.c_str());
   while (tmp[i]) {
        if (tmp[i] == s2[j]) {
            std::memmove(&tmp[i], &tmp[i + 1], strlen(tmp) - i);
            j++;
            good_count++;
            i = 0;
        } else
            i++;
      }
     return good_count == s2.size() ? true : false;
}

I thought about the memmove function, is it too slow ? I tried with std::remove and str.erase but i get the same results. Thank you for your help !

Answer 1

Your current metode is to actually do a rearrangement, with a lot of memory movement. But actually you could just count the amount of each letter in S2, then run through S1 until you have accumulated the same number of letters.

Achtung totally untested code.

// assuming all is lowercase
int matches = S2.length();
std::array<int, 256> chars { 0 };
for (char alfa : S2) {
  chars[alfa]++;
}
for (char alfa : S1) {
  if (chars[alfa]-->0) {
    if (!--matches)
      return true;
  }
}