The longest run with only two kinds
A packing line can hold two product types at once before it has to be cleaned down. Given the day’s sequence, find the longest run it could have handled without a change-over.
- A run is a stretch of consecutive items.
- The run may contain at most two distinct characters; one kind, or none, is also fine.
- Return the length of the longest such run.
- An empty sequence has a longest run of zero.
longestTwoFlavourRun(sequence: string) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int longestTwoFlavourRun(std::string sequence) {
}Worked examples
| Call | Result |
|---|---|
longestTwoFlavourRun(std::string("aabbcc")) | 4 |
longestTwoFlavourRun(std::string("abcbbbbcccbdddadacb")) | 10 |
longestTwoFlavourRun(std::string("aaaa")) | 4 |
longestTwoFlavourRun(std::string("ab")) | 2 |
Hint
Grow a window to the right, keeping a count per character inside it. When a third kind appears, pull the left edge in until one kind is gone.
Reference solution in C++
int longestTwoFlavourRun(std::string sequence) {
std::map<char, int> counts;
int left = 0, best = 0;
for (int right = 0; right < static_cast<int>(sequence.size()); right++) {
counts[sequence[right]]++;
while (counts.size() > 2) {
char out = sequence[left];
counts[out] -= 1;
if (counts[out] == 0) counts.erase(out);
left++;
}
if (right - left + 1 > best) best = right - left + 1;
}
return best;
}