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)
```