Why did my code timed out if required time complexity is met?

I tried to solve CodeWars kata and got stuck on the time out error. I read in the comments that the code should be O(n) complexity. Though, my code is actually O(n). So, maybe i had made some mistakes and so on. Why did not this work? Should anyone explain why my code is slower than O(n) pls?

#include <string>
using namespace std;

bool scramble(const std::string& s1, const std::string& s2)
{
    string copy = s1;
    int sum = 0;
    for (int i=0; i < s2.size(); ++i)
    {
        size_t found = copy.find(string(1,s2[i]));
        if (found != string::npos)
        {
            sum++;
            copy.erase(found,1);
        }
    }
    if (sum == s2.size()){return true;}
    return false;

}

Answer

The biggest issue I see is that copy.find() & copy.erase() are more expensive than you think. They are essentially O(n), and since it’s in a O(n) for loop, you have at least O(n^2) run time.

By counting letters, you can avoid that altogether. The code below is O(3n) –> O(n). It also passed all tests.

#include<string>
#include <array>

bool scramble(const std::string& s1, const std::string& s2){
  std::array<int, 26> s1LetterCounts{0};
  for (auto& i : s1) {
    ++s1LetterCounts[i - 'a'];
  }
  
  for (auto& i : s2) {
    --s1LetterCounts[i - 'a'];
  }
  
  for (auto& i : s1LetterCounts) {
    if (i < 0) {
      return false;
    }
  }
  
  return true;
}

The final if condition is to satisfy the substring requirement. s1 may contain characters that s2 doesn’t, so the loop where s2 decrements from the counting array may leave some positive counts, but it should never leave a negative.

I could likely do a little more with regards to performance (merge 2nd and 3rd loops), but it passed as-is.

Leave a Reply

Your email address will not be published. Required fields are marked *