Divide a garland of diamonds and rubies using up to 2 cuts
Filed under Google
Free read 1 of 3By the Necklace Splitting Theorem, for 2 types and 2 thieves, 2 cuts always suffice. One piece must have length n/2.
The question
Given a circular garland (or linear array) of 'D' (diamonds) and 'R' (rubies), where both counts d and r are even, determine if it can be split into two contiguous pieces using at most 2 cuts such that each piece contains exactly d/2 diamonds and r/2 rubies.
Constraints
- 1 <= garland.length <= 10^5.
- Total diamonds d and total rubies r are both even.
- The string contains only 'D' and 'R'.
Examples
- Input
- garland = "DDRR"
- Output
- true
- Why
- Cut between index 1 and 2: "DD" has 2 D, 0 R (unequal). But a cut of length 2 as a window "DR" gives 1 D, 1 R; remaining has 1 D, 1 R.
- Input
- garland = "DRDR"
- Output
- true
- Why
- Take the subsegment from index 0 to 1 ("DR"), leaving ("DR"). Both have 1 D and 1 R.
Approach
By the Necklace Splitting Theorem, for 2 types and 2 thieves, 2 cuts always suffice. One piece must have length n/2.
Maintain a fixed-size sliding window of length n/2 over the array (doubled for circularity).
Check if any window of size n/2 contains exactly d/2 diamonds. If it does, rubies will automatically equal r/2.
Because the count changes by at most 1 per slide, the count is guaranteed to hit d/2.
Solution
O(N) time, O(N) space
class Solution:
def canDivideGarland(self, s: str) -> bool:
n = len(s)
target_d = s.count('D') // 2
half_len = n // 2
# Circular array simulated by doubling
s_ext = s + s
curr_d = s_ext[:half_len].count('D')
if curr_d == target_d:
return True
for i in range(1, n):
if s_ext[i - 1] == 'D':
curr_d -= 1
if s_ext[i + half_len - 1] == 'D':
curr_d += 1
if curr_d == target_d:
return True
return False
Tips
- What they are testing: Tests mathematical insight into the Hobby-Rice theorem / Borsuk-Ulam theorem (necklace splitting) and sliding window technique.
- Common mistake: Overcomplicating the search to O(N^2) instead of realizing one piece must be of exact length (d+r)/2.
Follow-ups
- What if there's a third type of stone and up to 3 cuts allowed?
Related Google questions
Collected from public candidate posts and coding forums. Updated Nov 2026.