def minimum_substring_partition_equal_freq_brute_force(input_string):
    string_length = len(input_string)
    minimum_partitions = string_length + 1

    for number_of_partitions in range(1, string_length + 1):
        for partition_indices in find_all_partitions(string_length, number_of_partitions):
            is_valid_partition = True

            for partition_index in range(number_of_partitions):
                start_index = partition_indices[partition_index - 1] if partition_index > 0 else 0
                end_index = partition_indices[partition_index]
                substring = input_string[start_index:end_index]

                if not has_equal_character_frequency(substring):
                    is_valid_partition = False
                    break

            if is_valid_partition:
                minimum_partitions = min(minimum_partitions, number_of_partitions)

    return minimum_partitions if minimum_partitions <= string_length else -1

def find_all_partitions(string_length, number_of_partitions):
    if number_of_partitions == 1:
        yield [string_length]
        return

    if number_of_partitions == string_length:
        yield list(range(1, string_length + 1))
        return

    def generate_partitions(current_partition, remaining_partitions):
        if remaining_partitions == 1:
            yield current_partition + [string_length]
            return

        start_index = current_partition[-1] if current_partition else 0
        for index in range(start_index + 1, string_length - remaining_partitions + 2):
            yield from generate_partitions(current_partition + [index], remaining_partitions - 1)

    yield from generate_partitions([], number_of_partitions)

def has_equal_character_frequency(substring):
    if not substring:
        return True

    character_counts = {}
    for char in substring:
        character_counts[char] = character_counts.get(char, 0) + 1

    # If only one character in substring it is automatically true
    if len(character_counts) <= 1:
        return True

    first_frequency = list(character_counts.values())[0]

    # Check if all character frequencies are equal to first frequency
    for frequency in character_counts.values():
        if frequency != first_frequency:
            return False

    return True

# The core idea is to try every single possible way to split the given string
# We check each split to see if it meets our criteria for equal char frequencies
# Steps:
# 1. Start by considering a partition with just one piece
# 2. Next, try all possible ways to split the string into two pieces.
# 3. Continue by trying all possible ways to split the string into three pieces
# 4. For each possible way of splitting the string, check if each piece has the same number of occurrences of each character.
# 5. If a split satisfies the equal frequency requirement for every piece, save the number of pieces in that split.
# 6. After checking every possible split, find the smallest number of pieces among all the valid splits. This smallest number is the answer.

def min_substring_partition(input_string):
    number_of_parts = 0
    start_index = 0
    string_length = len(input_string)

    while start_index < string_length:
        end_index = start_index
        character_counts = {}

        # This loop expands the current substring
        while end_index < string_length:
            current_char = input_string[end_index]
            character_counts[current_char] = character_counts.get(current_char, 0) + 1

            # Check if all chars have equal frequency
            frequencies = list(character_counts.values())

            if len(frequencies) > 0 and all(frequency == frequencies[0] for frequency in frequencies):
                # Found a valid split point
                number_of_parts += 1
                start_index = end_index + 1

                # Break to start a new substring from next char
                break

            end_index += 1

        # No valid split found from the start index.
        if end_index == string_length:
            number_of_parts += 1
            break

    return number_of_parts