count the number of ways to partition an array into two equal sets..

equal-set-partitioning.py

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# pylint: disable=C0111


def solve(arr):
    fhalf = set()
    prefl, i = 0, 0

    for x in xrange(len(arr)):
        fhalf.add(arr[x])
        if len(fhalf) != prefl:
            prefl = len(fhalf)
            i = x
    w = i
    shalf = set()
    for x in xrange(len(arr) - 1, i, -1):
        shalf.add(arr[x])
        if len(shalf) == prefl:
            w = x
            break
    return max(w - i, 0)


def main():
    print solve([1, 5, 1])
    print solve([4, 1, 1, 2, 4, 2, 4, 1])


main()