Longest Alternating Substring Code Challenge

Question

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

Answer 1

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';
    }
}