Problems › JavaScript › patterns
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
Where you start
function longestTwoFlavourRun(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 JavaScript
function longestTwoFlavourRun(sequence) {
const counts = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < sequence.length; right += 1) {
const ch = sequence[right];
counts.set(ch, (counts.get(ch) ?? 0) + 1);
while (counts.size > 2) {
const out = sequence[left];
const left_n = counts.get(out) - 1;
if (left_n === 0) counts.delete(out);
else counts.set(out, left_n);
left += 1;
}
const span = right - left + 1;
if (span > best) best = span;
}
return best;
}