Compare it

Part 1

It’s going to be a long post, furthermore, it’ll include code, I’ve warned you.
I took a simple task that I found on a popular platform called Leetcode. Write a function taking a string and returning a Boolean value, it should return true if all the symbols in the string occur the same amount of times, otherwise, it returns false, its length is between 1 and 1000, and only English lower-case letters are allowed. Leetcode provides a convenient web-based interface with buttons “Run” and “Submit”, everything that we need just to write code and then it’ll tell us whether it’s correct or not, and if it is we’ll see how fast it works.

The task is simple, the task is understood, basically speaking, we need two cycles: the first one to count occurrences and to store them somewhere and another one to check the stored occurrences. The complexity of the first cycle is O(n), where n is the length of the string, and the complexity of another one is O(1), because the English alphabet consists of 26 letters.

Ask ourselves: “What should we try to use in a C++ program?” – right: “Standard library”. Leetcode hints the same providing a starch of the solution with the string represented as a std::string rather than old-fashioned char*. However, what does a std string provide to help us solve this task? Well, since the C++11 standard, there is a range-based for loop, perhaps, that’s all. Let’s look at the code:

    bool areOccurrencesEqual(string s) {
        map<char, int> dict;
        for (const auto& ch: s)
        {
            auto it = dict.find(ch);

            if (dict.end() == it)
            {
                dict[ch] = 1;
            }
            else
            {
                ++it->second;
            }
        }

        int count = 0;

        for (const auto& [_, value]: dict)
        {
            if (count != value && count)
            {
                return false;
            }

            if (!count)
            {
                count = value;
            }
        }

        return true;
    }

This is an absolutely straightforward solution: we’ve done what we’ve written, first, it iterates over the string counting letters and storing the frequencies into the dict, and then it iterates over the dict, comparing the frequencies, also we took into account that initially the count is zero, so we should carefully assign in the loop encountering the first non-zero value.

There is a catch: this solution beats only 27 percent of its competitors, barely I’d decide to write about such a bleak result:)

#IT #c_plus_plus #leetcode #today #ToBeContinued

#IT #leetcode #c_plus_plus #ToBeContinued