Problem · String

Non-Alternating Binary Partitions

Learn this problem
MediumThe D. E. Shaw GroupOA

Problem statement

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 = 4return = 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.

More The D. E. Shaw Group problems

drafts saved locally
public int minNonAlternatingPartitions(String s, int frame) {
  // write your code here
}
s"101101"
frame4
expected3
checking account