Non-Alternating Binary Partitions

You are given a binary string s and an integer frame. Split s into the minimum number of non-overlapping contiguous substrings so that every substring satisfies both rules:
Its length is at most frame.
It is not perfectly alternating.
A perfectly alternating substring changes bit at every adjacent position, such as 01, 10, or 1010. The source sample uses single-character substrings in a valid answer, so FastPrep treats a single-character substring as allowed.

Function
minNonAlternatingPartitions(s: String, frame: int) → int

Examples
Example 1
s = "101101"
frame = 4
return = 3
One optimal split is 1011 | 0 | 1. The first part has length 4 and is not perfectly alternating; the source accepts the single-character pieces, giving 3 substrings.

Think of it as a minimum-cuts DP over prefixes. Let dp[i] be the fewest pieces covering the first i characters. For each i, you look back at starting points j with i - j <= frame, and a piece s[j..i) is valid if it's length 1 or it contains at least one pair of equal adjacent bits. Precompute for each position the nearest equal-adjacent pair so the validity check is O(1), which keeps the whole thing around O(n * frame) or better. The pitfall is the single-character rule. A lone bit is never alternating in the strict sense, but this problem allows it, so don't reject it. Another trap is checking alternation by scanning the substring each time, which turns it cubic. A greedy take-the-longest-piece approach can also fail, so verify it against the example 101101 with frame 4, which gives 3. If the DP transitions slip away mid-assessment, StealthCoder is your hedge.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.