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
Go 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
func longestTwoFlavourRun(sequence string) int {
}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 Go
func longestTwoFlavourRun(sequence string) int {
counts := map[rune]int{}
chars := []rune(sequence)
left, best := 0, 0
for right := 0; right < len(chars); right++ {
counts[chars[right]]++
for len(counts) > 2 {
counts[chars[left]]--
if counts[chars[left]] == 0 {
delete(counts, chars[left])
}
left++
}
if right-left+1 > best {
best = right - left + 1
}
}
return best
}