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
public int LongestTwoFlavourRun(string sequence) {
}Worked examples
| Call | Result |
|---|---|
LongestTwoFlavourRun("aabbcc") | 4 |
LongestTwoFlavourRun("abcbbbbcccbdddadacb") | 10 |
LongestTwoFlavourRun("aaaa") | 4 |
LongestTwoFlavourRun("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#
public int LongestTwoFlavourRun(string sequence) {
var counts = new Dictionary<char, int>();
int left = 0, best = 0;
for (int right = 0; right < sequence.Length; right++) {
char ch = sequence[right];
counts[ch] = counts.ContainsKey(ch) ? counts[ch] + 1 : 1;
while (counts.Count > 2) {
char outCh = sequence[left];
counts[outCh] -= 1;
if (counts[outCh] == 0) counts.Remove(outCh);
left++;
}
best = Math.Max(best, right - left + 1);
}
return best;
}