Why it took 54 ms even though the time complexity was O(n) [closed]

Question

I recenty started solving questions on leetcode and came accross this Questions where we had to remove all alphanumeric characters from a string and then check if the string is a palindrome or not. I tried to keep O(n) time complexity still it took 54 ms which is way too long can someone please explain. Here is the code:

class Solution {
public:
    bool isPalindrome(string s) {
        int n = 0;
        transform(s.begin(),s.end(),s.begin(),::tolower);
        while(s[n] != '\0'){
            if(isalnum(s[n]) == 0 ){
                s.erase(s.begin()+n);
            }
            else{
            n++;
            }
        }

        string check = s;
        reverse(s.begin(),s.end());

        if(s == check){
            return true;
        }
        else{
            return false;
        }

    }
};

I was wanted to know what part of code exaclty is taking time

Answer 1

The complexities of all parts:

• Transforming to lowercase: O(N)
• Removing non-alphanumeric characters: O(N^2)
• Reversing the string: O(N)
• Comparing strings: O(N)

You can use two pointers with O(N) time complexity:

#include <iostream>
#include <cstdint>
#include <string>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto improve_runtime = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

struct Solution
{
    static bool isPalindrome(const std::string &s)
    {
        for (int left = 0, right = s.size() - 1; left < right; ++left, --right)
        {
            while (left < right && !std::isalnum(s[left]))
            {
                ++left;
            }

            while (left < right && !std::isalnum(s[right]))
            {
                --right;
            }

            if (std::toupper(s[left]) != std::toupper(s[right]))
            {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    std::cout << std::boolalpha << Solution().isPalindrome("A man, a plan, a canal: Panama") << "\n";
    std::cout << std::boolalpha << Solution().isPalindrome("A Santa at NASA") << "\n";
    std::cout << std::boolalpha << Solution().isPalindrome("Taco Cat") << "\n";
    std::cout << std::boolalpha << Solution().isPalindrome("Was it a cat I saw?") << "\n";
    std::cout << std::boolalpha << Solution().isPalindrome("Never odd or even") << "\n";
}

Prints

true
true
true
true
true

Comment:

• std::isalnum returns 0 when the argument is not alpha-numeric, and non-zero when it is. While false is equal to 0, non-zero is not necessarily equal to true. So comparing with false is a bit misleading, since the type of the result is not bool; compare with 0, which is what the function actually returns. Or use the usual !isalnum(whatever). – Pete Becker

• Why std::int_fast16_t? This makes code slower. – Marek R

Answer 2

Calling erase repeatedly is probably an inefficient way of doing this. When you use call erase on one character, the machine has to move all the following characters one space to the left. This is an O(n) operation. For example, erasing the 'E' in "HELLO" would require the computer to complete all these steps:

0 1 2 3 4
H E L L O

0 1 2 3 4
H   L L O

0 1 2 3 4
H L   L O

0 1 2 3 4
H L L   O

0 1 2 3 4
H L L O

Since you've embedded an erase call in a loop that iterates over your string, your time complexity is O(n*n)=O(n²).

You'll need to find some other way of filtering out the alphanumerics - that much is up to you.