Skip to content

Instantly share code, notes, and snippets.

@aberke
Created March 1, 2017 15:42
Show Gist options
  • Save aberke/66614009ee351f6b714fe409b1bf35de to your computer and use it in GitHub Desktop.
Save aberke/66614009ee351f6b714fe409b1bf35de to your computer and use it in GitHub Desktop.
Solution to Hacker Rank Challenge: Xaero And Palindromic Strings -- Finds probability of palindromic substrings when a given string
"""
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment