ab.cpp

#define CATCH_CONFIG_MAIN
#include "catch.hpp"

#include <string>
#include <map>
#include <cctype>

const int MAX_ALLOWED_LETTERS = 2;

// Checks whether [current_left, current_right) is a longer string than [max_left, max_left + max_length).
// If it is, updates max_left and max_length.
inline void check_new_substring(const int &current_left, 
	                            const int &current_right,
	                            int &max_left,
	                            int &max_length)
{
	int current_length = current_right - current_left;
	if (current_length > max_length) {
		max_left = current_left;
		max_length = current_length;
	}
}

// Finds the longest substring that consists only of two (or less) distinct letters.
// If there is no such substring, returns "".
// If there are more than one such substring, returns the first one.
// Time is O(src.size()) since the total number of inner loop iterations is no more than src.size().
// Space is O(1).
std::string longest_two_letter_substring(const std::string &src)
{	
	int length = src.size();
	int max_left = 0, max_length = 0;
	int current_left = 0, current_right = 0;

	std::map<char, int> char_counter;

	for (int current_right = 0; current_right < length; current_right++) {
		char c = src[current_right];

		if (!isalpha(c)) {
			// check whether we have a new longest substring
			check_new_substring(current_left, current_right, max_left, max_length);

			// start a new substring
			current_left = current_right + 1;
			char_counter.clear();
		} else {
			++char_counter[c];
			if (char_counter.size() > MAX_ALLOWED_LETTERS) {
				// check whether we have a new longest substring
				check_new_substring(current_left, current_right, max_left, max_length);

				// search for where to start a new substring
				while (char_counter.size() > MAX_ALLOWED_LETTERS) {
					char left_char = src[current_left++];
					--char_counter[left_char];
					if (char_counter[left_char] == 0) {
						char_counter.erase(left_char);
					}
				}
			}
		}
	}

	if (isalpha(src[length - 1])) {
		current_right = length;
		check_new_substring(current_left, current_right, max_left, max_length);
	}

	return src.substr(max_left, max_length);
}

TEST_CASE("Longest substring consisting of no more than two distinct letters") {
	REQUIRE(longest_two_letter_substring("") == "");
	REQUIRE(longest_two_letter_substring("abc") == "ab");
	REQUIRE(longest_two_letter_substring(" ") == "");
	REQUIRE(longest_two_letter_substring("  ") == "");
	REQUIRE(longest_two_letter_substring("   ") == "");
	REQUIRE(longest_two_letter_substring("    ") == "");
	REQUIRE(longest_two_letter_substring("a1") == "a");
	REQUIRE(longest_two_letter_substring("1z") == "z");
	REQUIRE(longest_two_letter_substring("a1bc") == "bc");
	REQUIRE(longest_two_letter_substring("ab2bc") == "ab");
	REQUIRE(longest_two_letter_substring("aaaaa") == "aaaaa");
	REQUIRE(longest_two_letter_substring("aaaaab") == "aaaaab");
	REQUIRE(longest_two_letter_substring("aaaaabcccccccc") == "bcccccccc");
	REQUIRE(longest_two_letter_substring("aaaaaxcccccbb") == "cccccbb");
	REQUIRE(longest_two_letter_substring(" abababababxxxxxx                  z") == "ababababab");
	REQUIRE(longest_two_letter_substring("ababxxxxxxaa") == "xxxxxxaa");
	REQUIRE(longest_two_letter_substring("ababbxxxxxxa") == "bbxxxxxx");
	REQUIRE(longest_two_letter_substring("abcabcabcabc") == "ab");
	REQUIRE(longest_two_letter_substring("XXxxYY") == "XXxx");
	REQUIRE(longest_two_letter_substring("aa aa aa aa") == "aa");
	REQUIRE(longest_two_letter_substring("abccccca") == "bccccc");
}

Makefile

CXXFLAGS += -std=c++11 -Wall -Werror -Wpedantic

.PHONY: test
test: all
	./ab -s
all: ab