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