2
\$\begingroup\$

I'm still new to C++ and tried one of the harder challenges on a coding practice/challenge website. The challenge was the following:

Given a string of digits, return the longest substring with alternating odd/even or even/odd digits. If two or more substrings have the same length, return the substring that occurs first.

I was able to solve it in ~ 50 minutes, but I feel like my code is really sloppy. Can anyone give me tips on how to simplify this? I find myself falling into very complex ways of solving things often.

std::string longestSubstring(std::string digits) {
    std::string strOddEven{};
    std::vector<std::string> vecOddEven{};
    bool next{};
    int maxSize{};

    for (int i = 0; i < digits.size() - 1; ++i)
    {
        if ((digits.at(i) % 2 == 0 && digits.at(i + 1) % 2 != 0) ||
            (digits.at(i) % 2 != 0 && digits.at(i + 1) % 2 == 0))
        {
            strOddEven += digits.at(i);
            next = true;
            if (i == digits.size() - 2)            // add to strOddEven and push_back 
            {                                      // in case of longest string being at end
                strOddEven += digits.at(i + 1);
                vecOddEven.push_back(strOddEven);
            }
        }
        else if (next)
        {
            strOddEven += digits.at(i);
            vecOddEven.push_back(strOddEven);
            strOddEven = "";
            next = false;
        }
    }

    for (auto& i : vecOddEven)
        if (i.size() > maxSize)
            maxSize = i.size();

    for (auto& i : vecOddEven)
        if (i.size() == maxSize)
            return i;
}
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Include the headers we need

#include <string>
#include <vector>

Don't make unnecessary copies

std::string longestSubstring(const std::string& digits) {

Also, consider storing std::string_view objects internally, as these are much lighter than owning strings.

Fix the bug

I get a SIGABRT when I call with empty string as argument:

==1629582==    by 0x4914B54: __cxa_throw (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==1629582==    by 0x490C090: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28)
==1629582==    by 0x10AC0B: std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::at(unsigned long) const (basic_string.h:1087)
==1629582==    by 0x10A30F: longestSubstring(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (238652.cpp:12)
==1629582==    by 0x10A725: main (238652.cpp:46)

Use the algorithm library

The standard <algorithm> library has the tools you need, that will save you writing much tedious and error-prone code for yourself.

The most useful function here is std::adjacent_find(), which you can use with a simple predicate such as

auto const both_even_or_both_odd
    = [](auto a, auto b){ return a % 2 == b % 2; };

No need to store all the substrings

We only need to remember the longest substring seen so far, so there's no need for the two vectors. Just have a single std::string_view variable that you update when you find a longer run than the existing one.


Modified version

Here's a version using std::adjacent_find() as suggested:

#include <algorithm>
#include <string>
#include <utility>
#include <vector>

std::string longestSubstring(const std::string& digits)
{
    std::string longest = "";

    auto const same_mod2 = [](auto a, auto b){ return a % 2 == b % 2; };

    auto start = digits.begin();
    while (start < digits.end()) {
        auto finish = std::adjacent_find(start, digits.end(), same_mod2);
        if (finish != digits.end()) {
            ++finish;
        }
        auto const candidate = std::string{start, finish};
        if (candidate.size() > longest.size()) {
            longest = std::move(candidate);
        }
        start = finish;
    }

    return std::string{longest};
}

And a simple test:

#include <iostream>

int main()
{
    for (auto const& s: { "", "0", "11", "01", "112",
                          "0112", "01224", "01223", "01123" }) {
        std::cout << s << "-->" << longestSubstring(s) << '\n';
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.