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
Java 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(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 Java
int longestTwoFlavourRun(String sequence) {
Map<Character, Integer> counts = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < sequence.length(); right++) {
char ch = sequence.charAt(right);
counts.merge(ch, 1, Integer::sum);
while (counts.size() > 2) {
char out = sequence.charAt(left);
int remaining = counts.get(out) - 1;
if (remaining == 0) counts.remove(out);
else counts.put(out, remaining);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}