Sharing answer codes of mine about HackerRank: Short Palindrome.

HackerRank: Short Palindrome (in Algorithm)

Problem Statement

Consider a string, , of lowercase English letters where each character, , denotes the letter at index in . We define an palindromic tuple of to be a sequence of indices in satisfying the following criteria:

  • , meaning the characters located at indices and are the same.
  • , meaning the characters located at indices and are the same.
  • , meaning that and are ascending in value and are valid indices within string .

Given , find and print the number of tuples satisfying the above conditions. As this value can be quite large, print it modulo .

Naive Answer Code (in Python3)

  • Time complexity:
# Time complexity: O(n^3)
#!/bin/python3

import sys
import string

def shortPalindrome(s):
    mod = pow(10,9)+7
    cnt = 0

    for i in range(len(s)):
        for j in range(i+1, len(s)):
            for k in range(j+1, len(s)):
                if s[j]==s[k]:
                    cnt += s[k+1:].count(s[i])

    return cnt % mod

if __name__ == "__main__":
    s = input().strip()
    result = shortPalindrome(s)
    print(result)

Final Answer Code (in Python3)

  • Time complexity:
# Time complexity: O(n)
#!/bin/python3

import sys
import string

def shortPalindrome(input_string):
    c_dic = dict(zip(string.ascii_lowercase, range(26)))  # ascii value dict for every alphabet
    ip_ascii = [c_dic[i] for i in input_string]  # change input as ascii value
    one_c = [0] * 26  # for one character occurred (e.g. a)
    two_c = [[0] * 26 for _ in range(26)]  # for two chracter occurred (e.g. ab)
    thr_c = [0] * 26  # for three chracter occured following the rule (e.g. abb)
    total = 0

    for current in ip_ascii:
        # sum the number of matching palindrome when the last character is 'current' (e.g. abba)
        total += thr_c[current]
        for i in range(26):  # for every alphabet, sum the number of sequence such as 'abb'
            thr_c[i] += two_c[i][current]
        for i in range(26):  # for every alphabet, sum the number of sequence such as 'ab'
            two_c[i][current] += one_c[i]
        one_c[current] += 1  # Count the occurred character

    return total % (10 ** 9 + 7)

if __name__ == "__main__":
    s = input().strip()
    result = shortPalindrome(s)
    print(result)