# Longest Alternating Substring Code Challenge

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


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