โ† Google questions

Divide a garland of diamonds and rubies using up to 2 cuts

Filed under Google

Free read 1 of 3

By 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

  1. By the Necklace Splitting Theorem, for 2 types and 2 thieves, 2 cuts always suffice. One piece must have length n/2.

Solution

O(N) time, O(N) space

Python
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.