Looking at this problem, I need to understand that:
- Each day, Polycarp can remember at most 3 different letters
- He must write the string in order, adding characters to the end
- Need to find minimum days
**Greedy approach:**
- Keep track of letters memorized in the current day
- For each character: if already in memory, write it; if not in memory but space available, add it; if memory is full, start a new day with this character
Let me trace through the examples:
- "lollipops": Day 1 memorizes {l,o,i} writes "lolli", Day 2 memorizes {p,o,s} writes "pops" → 2 days ✓
- "stringology": Day 1 {s,t,r} writes "str", Day 2 {i,n,g} writes "ing", Day 3 {o,l,g} writes "olog", Day 4 {y} writes "y" → 4 days ✓
The key insight: when starting a new day, we reset memory and begin fresh with just the current character, allowing us to add up to 2 more different letters during that day.
```go
package main
import "fmt"
func main() {
var t int
fmt.Scan(&t)
for i := 0; i < t; i++ {
var s string
fmt.Scan(&s)
days := 1
count := 0
seen := [26]bool{}
for j := 0; j < len(s); j++ {
idx := s[j] - 'a'
if !seen[idx] {
if count == 3 {
days++
seen = [26]bool{}
count = 0
}
seen[idx] = true
count++
}
}
fmt.Println(days)
}
}
```