Valleys and Hills

Chef built a binary string $S$ that has exactly $N$ hills and $M$ valleys. - A **hill** is any index $1 \lt i \lt |S|$ such that both its neighbors are strictly smaller than it, i.e, $S_{i-1} \lt S_i$ and $S_{i+1} \lt S_i$. - A **valley** is any index $1 \lt i \lt |S|$ such that both its neighbors are strictly larger than it, i.e, $S_{i-1} \gt S_i$ and $S_{i+1} \gt S_i$. Chef thinks that his st