Solution to Hacker Rank Challenge: Xaero And Palindromic Strings -- Finds probability of palindromic substrings when a given string

xaero_and_palindromic_strings.py

"""
Alex Berke (aberke)

Problem:
--------
https://www.hackerrank.com/contests/101hack29/challenges/xaero-and-palindromic-strings/copy-from/1300744544

A string  is called a palindromic string if it can be read the same going forward as well as backwards.
What is the probability of choosing a substring of  such that the letters of the chosen substring can be
shuffled to make it a palindromic string?

Input Format

First line of input contains a single integer T denoting the number of test cases.
First and only line of each test case contains a string  consisting of lower case alphabet letters.

Output Format

For each test case, print the required probability in the form of an irreducible ratio P/Q.

Sample Input
------------
3
hacker
aaaaa
racer

Sample Output
-------------
2/7
1/1
1/3
"""

import sys


def main():
    count = int(sys.stdin.readline().strip())
    seen = 0
    while seen < count:
        string = sys.stdin.readline().strip()
        handle_string(string)
        seen += 1


def handle_string(string):
    s_length = len(string)
    numerator = 0
    denominator = calculate_denominator(s_length)

    for i in range(s_length):
        histogram = set()
        for j in range(i, s_length):
            letter = string[j]
            handle_new_letter(histogram, letter)
            if is_eligible_substring(histogram):
                numerator += 1

    numerator, denominator = reduce(numerator, denominator)
    print('{}/{}'.format(numerator, denominator))
    return (numerator, denominator)


def handle_new_letter(histogram, letter):
    if letter in histogram:
        histogram.remove(letter)
    else:
        histogram.add(letter)
    return histogram


def is_eligible_substring(histogram):
    return len(histogram) < 2


def gcd(a, b):
    while b != 0:
        t = b
        b = (a % b)
        a = t
    return a


def reduce(numerator, denominator):
    quotient = gcd(numerator, denominator)
    return (numerator//quotient, denominator//quotient)


def calculate_denominator(string_length):
    return ((string_length + 1)*string_length)//2


if __name__ == "__main__":
    main()