Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Custom LeetCode-style prompt: Two-Color Necklace Splitting
• Topics: Array, Sliding Window, Prefix Sum, Greedy, Math

Problem gist

This is a special case of the necklace splitting problem: two people, two bead types, and therefore at most two cuts. The input is a necklace represented as an array containing only X and Y. Suppose the full array has:

• a occurrences of X
• b occurrences of Y

The goal is to cut the array into either two or three contiguous subarrays, then allocate those pieces to two people so that each person receives exactly:

• a / 2 occurrences of X
• b / 2 occurrences of Y

This only makes sense when both a and b are even. If either count is odd, no integer split can give both people exactly half of that type.

In the code below, cut indices are zero-based exclusive boundaries:

• returning [i] means arr[:i] and arr[i:]
• returning [i, j] means arr[:i], arr[i:j], and arr[j:]

For a two-cut answer, the middle piece goes to one person and the two outside pieces go to the other person.

Key reduction

The important observation is that it is enough to find one contiguous subarray that already contains exactly half of the Xs and half of the Ys.

If such a subarray is at the edge, one cut creates two pieces. Give the target subarray to one person and the remaining suffix or prefix to the other.

If such a subarray is in the middle, two cuts create three pieces. Give the middle target subarray to one person and the two outer pieces to the other. The outer pieces together must contain the remaining half of both symbols.

So the problem becomes:

find a contiguous window with a / 2 Xs and b / 2 Ys.

Because that target window has (a + b) / 2 total elements, its length is fixed: exactly half of the array length. That means the whole problem is a fixed-size sliding-window scan.

Why a solution always exists when both counts are even

Let n be the array length and m = n / 2. Look at every window of length m. Define x_count(start) as the number of Xs in the window:

arr[start : start + m]

The first length-m window and the last length-m window are complementary:

• first window: arr[0:m]
• last window: arr[m:n]

Together they cover the whole array, so their X counts add up to a.

If the first window has more than a / 2 Xs, the last one has fewer than a / 2. If the first has fewer, the last has more. Moving the window one step at a time changes the X count by at most one, because one element leaves and one element enters.

So at some position, the window must hit exactly a / 2 Xs. Since the window length is fixed at n / 2, it automatically has exactly b / 2 Ys too.

That is the two-color, two-person special case of the necklace-splitting idea.

Python solution

from typing import List, Sequence


class TwoColorNecklaceSplitter:
    """
    Find cut indices for the two-color, two-person necklace-splitting case.

    Cut positions are zero-based exclusive boundaries. For example:
    cuts [2, 6] split arr into arr[:2], arr[2:6], and arr[6:].
    """

    def __init__(self, x_symbol: str = "X", y_symbol: str = "Y") -> None:
        self.x_symbol = x_symbol
        self.y_symbol = y_symbol

    def find_cut_indices(self, values: Sequence[str]) -> List[int]:
        total_x = self._count_symbol(values, self.x_symbol)
        total_y = self._count_symbol(values, self.y_symbol)

        if total_x + total_y != len(values):
            raise ValueError("Input must contain only the configured necklace symbols.")

        if total_x % 2 != 0 or total_y % 2 != 0:
            return []

        target_length = len(values) // 2
        target_x_count = total_x // 2

        if target_length == 0:
            return []

        window_x_count = self._count_symbol(
            values[:target_length],
            self.x_symbol,
        )

        if window_x_count == target_x_count:
            return self._cuts_for_target_window(0, target_length, len(values))

        for start_index in range(1, len(values) - target_length + 1):
            outgoing_value = values[start_index - 1]
            incoming_value = values[start_index + target_length - 1]

            if outgoing_value == self.x_symbol:
                window_x_count -= 1
            if incoming_value == self.x_symbol:
                window_x_count += 1

            if window_x_count == target_x_count:
                end_index = start_index + target_length
                return self._cuts_for_target_window(
                    start_index,
                    end_index,
                    len(values),
                )

        # For valid two-color input with even counts, the proof above says this
        # should not be reached. Returning [] keeps the API safe for bad inputs.
        return []

    def _count_symbol(self, values: Sequence[str], target_symbol: str) -> int:
        return sum(value == target_symbol for value in values)

    def _cuts_for_target_window(
        self,
        start_index: int,
        end_index: int,
        array_length: int,
    ) -> List[int]:
        cut_indices: List[int] = []

        if start_index > 0:
            cut_indices.append(start_index)
        if end_index < array_length:
            cut_indices.append(end_index)

        return cut_indices


class Solution:
    def splitNecklace(self, values: List[str]) -> List[int]:
        return TwoColorNecklaceSplitter().find_cut_indices(values)

The time complexity is O(n): the algorithm counts symbols once and then slides one fixed-size window across the array. The extra space complexity is O(1) apart from the returned cut list.

Common mistakes

A common mistake is to search for any window with a / 2 Xs and b / 2 Ys using a variable-size two-pointer window. That works, but it misses the stronger structure: any valid half-share window must have length exactly n / 2. Recognizing the fixed length makes the implementation simpler.

Another mistake is to return only the middle window boundaries without defining the allocation rule. With two cuts [i, j], the intended allocation is:

• person 1 gets arr[i:j]
• person 2 gets arr[:i] and arr[j:]

The cuts alone are enough only if that convention is clear.

Interview follow-ups

Can this be solved with prefix sums instead of a sliding window?

Yes. Build a prefix count of Xs, where prefix_x[i] is the number of Xs in arr[:i]. Then each length-n / 2 window has:

prefix_x[start + n / 2] - prefix_x[start]

Xs. Scan all possible starts and return the first one whose count is a / 2. The time complexity is still O(n), but the space complexity becomes O(n). The sliding-window version is usually better because it keeps only one running count.

What if the array contains more than two item types?

For a fixed number of item types, the same high-level idea still applies: find a contiguous window that contains half of every type. The target window length is still n / 2, so a fixed-size sliding window can maintain a frequency map for all types in the current window.

The scan costs O(n * t) if each window comparison checks all t types, or O(n) if the implementation maintains a count of how many types currently match their target frequencies. The extra space becomes O(t).

The deeper theorem says that with t item types and two people, t cuts are enough. For this problem, t = 2, which is why two cuts, or three pieces, are enough.

What if the interviewer asks for the actual allocation, not just cuts?

Return both the cuts and the ownership of each resulting segment. If the target window is [start, end), then:

• when start == 0, person 1 gets segment 0, person 2 gets segment 1
• when end == n, person 1 gets segment 1, person 2 gets segment 0
• otherwise, person 1 gets the middle segment and person 2 gets the outer two

The algorithm does not change. The only difference is the return type, such as a small object containing cuts, person_one_segments, and person_two_segments.

What if a or b is odd?

Then an exact fair split is impossible under the stated requirement, because one person would need a fractional number of that symbol. A production API should return no answer, raise a validation error, or define a nearest-fair objective.

If the requirement changes to “as balanced as possible,” the problem is no longer this clean fixed-target scan. One practical approach is to still inspect length-n / 2 windows and minimize the imbalance score, such as:

abs(window_x - a / 2) + abs(window_y - b / 2)

The runtime stays linear for two symbols, but the output semantics become a policy choice rather than an exact theorem.