# 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;

}
```

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.