Given string s, the task is to find the count of all substrings which have the same character at the beginning and end.
Example 1:
Input: s = "abcab"
Output: 7
Explanation: a, abca, b, bcab, 
c, a and b
Example 2:
Input: s = "aba"
Output: 4
Explanation: a, b, a and aba
User Task:
Your task is to complete the function countSubstringWithEqualEnds() which takes a single string as input and returns the count. You do not need to take any input or print anything.
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(constant)
Constraints:
1 <= |s| <= 10^{4}
s contains lower case english alphabets

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(constant)

Starter code:
#User function Template for python3

class Solution:

	def countSubstringWithEqualEnds(self, s):

		# code here

Solutions:
class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		c = 0
		for i in s:
			if i not in d:
				d[i] = 0
			d[i] += 1
			c += d[i]
		return c


import re
from collections import Counter

class Solution:

	def countSubstringWithEqualEnds(self, s):
		c = Counter(s)
		count = 0
		for item in c:
			count += c[item] * (c[item] + 1) // 2
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		hash = {}
		for i in s:
			hash[i] = hash.get(i, 0) + 1
		count = 0
		for i in hash:
			count += hash[i] * (hash[i] + 1) // 2
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		l = [0] * 26
		count = 0
		for i in range(len(s)):
			l[ord(s[i]) - ord('a')] += 1
		for i in range(len(l)):
			count += l[i] * (l[i] + 1) // 2
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		rpt = 0
		uni = 0
		for i in s:
			if i not in h:
				h[i] = 1
				uni += 1
			else:
				h[i] += 1
				rpt += h[i]
		return rpt + uni


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = [0] * 26
		ans = 0
		for c in s:
			if count[ord(c) - ord('a')] > 0:
				ans += count[ord(c) - ord('a')]
			count[ord(c) - ord('a')] += 1
			ans += 1
		return ans


class Solution:

	def countSubstringWithEqualEnds(self, s):
		dict1 = {}
		c = 0
		rep = 0
		for i in s:
			if i not in dict1:
				dict1[i] = 1
				c += 1
			else:
				dict1[i] += 1
				rep += dict1[i]
		return c + rep


from collections import Counter

class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = 0
		s = Counter(s)
		for i in s:
			count += s[i] * (s[i] + 1) // 2
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		ctr = 0
		mp = {}
		count = 0
		for i in s:
			if i in mp:
				mp[i] += 1
				count += mp[i]
			else:
				mp[i] = 1
				ctr += mp[i]
		return ctr + count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		rept = 0
		unique = 0
		for i in s:
			if i not in h:
				h[i] = 1
				unique += 1
			else:
				h[i] += 1
				rept += h[i]
		return rept + unique


class Solution:

	def countSubstringWithEqualEnds(self, s):
		from collections import Counter
		d = Counter(s)
		c = 0
		for (i, j) in d.items():
			c = c + j * (j + 1) // 2
		return c


from collections import Counter

class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		rpt = 0
		unique = 0
		for i in s:
			if i not in h:
				h[i] = 1
				unique += 1
			else:
				h[i] += 1
				rpt = rpt + h[i]
		return rpt + unique


class Solution:

	def countSubstringWithEqualEnds(self, s):
		x = [0] * 26
		z = 0
		for i in s:
			x[ord(i) - 97] += 1
		for j in x:
			z += j * (j + 1) / 2
		return int(z)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		alpha = [0] * 26
		result = 0
		for i in s:
			alpha[ord(i) - 97] += 1
		for i in alpha:
			result += i * (i + 1) / 2
		return int(result)


import itertools

class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		rpt = 0
		unique = 0
		for i in s:
			if i not in h:
				h[i] = 1
				unique += 1
			else:
				h[i] += 1
				rpt = rpt + h[i]
		return rpt + unique


class Solution:

	def countSubstringWithEqualEnds(self, s):
		subst = {}
		count = 0
		for i in range(0, len(s)):
			if subst.get(s[i]) == None:
				subst[s[i]] = 1
				count += 1
			else:
				subst[s[i]] += 1
				count += subst[s[i]]
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = 0
		hash = {}
		for i in range(len(s)):
			if s[i] in hash.keys():
				hash[s[i]] += '1'
			else:
				hash.update({s[i]: '1'})
		for v in hash.values():
			count += len(v) * (len(v) + 1) / 2
		return int(count)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		freq = dict()
		count = 0
		for let in s:
			try:
				freq[let] += 1
			except KeyError:
				freq[let] = 1
		for value in freq.values():
			count += value * (value - 1) // 2
		count += len(s)
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = dict()
		sum = 0
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			sum += d[i]
		return sum


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d1 = [0] * 26
		for i in s:
			d1[ord(i) - ord('a')] += 1
		res = 0
		for i in d1:
			if i >= 1:
				res += i * (i + 1) // 2
		return res


class Solution:

	def countSubstringWithEqualEnds(self, s):
		cnt = 0
		lst = [0] * (26 + 1)
		for i in s:
			lst[ord(i) - 97] += 1
		for i in lst:
			if i != 0:
				cnt = cnt + i * (i + 1) // 2
		return cnt


class Solution:

	def countSubstringWithEqualEnds(self, s):
		a = set(s)
		sum = 0
		for i in a:
			c = s.count(i)
			sum += int(c * (c + 1) / 2)
		return sum


class Solution:

	def countSubstringWithEqualEnds(self, s):
		dict = {}
		unique = 0
		repeat = 0
		for i in range(len(s)):
			if s[i] not in dict:
				dict[s[i]] = 1
				unique += 1
			else:
				dict[s[i]] += 1
				repeat = repeat + dict[s[i]]
		return unique + repeat


MAX_CHAR = 26

class Solution:

	def countSubstringWithEqualEnds(self, s):
		result = 0
		n = len(s)
		count = [0] * MAX_CHAR
		for i in range(n):
			count[ord(s[i]) - ord('a')] += 1
		for i in range(MAX_CHAR):
			result += count[i] * (count[i] + 1) // 2
		return result


import collections

class Solution:

	def countSubstringWithEqualEnds(self, s):
		mapp = collections.defaultdict(int)
		count = 0
		for i in range(len(s)):
			mapp[s[i]] += 1
		for ch in mapp:
			val = mapp[ch]
			count += val * (val + 1) // 2
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		li = []
		count = 0
		for i in s:
			d[i] = d.get(i, 0) + 1
		for i in d:
			li.append(d.get(i))
		for i in range(len(li)):
			if li[i] > 1:
				count = count + li[i] * (li[i] - 1) // 2
		count += len(s)
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		from collections import defaultdict
		d = defaultdict(int)
		for i in s:
			d[i] += 1
		total = 0
		total += len(s)
		for i in d.keys():
			total += d[i] * (d[i] - 1) // 2
		return total


class Solution:

	def countSubstringWithEqualEnds(self, s):
		output = len(s)
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for x in dic.values():
			if x > 1:
				output += x * (x + 1) // 2 - x
		return output


def factorial(n):
	return int(n * (n - 1) / 2)

class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		x = len(s)
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d.values():
			x = x + factorial(i)
		return x


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = 0
		for i in set(s):
			occ = s.count(i)
			count += occ * (occ - 1) // 2
		return len(s) + count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		dict = {}
		count = 0
		for i in range(len(s)):
			if s[i] in dict:
				dict[s[i]] += 1
				count = count + dict.get(s[i])
			elif s[i] not in dict:
				dict[s[i]] = 1
				count = count + dict.get(s[i])
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		sum = 0
		for i in range(len(s)):
			if s[i] in d.keys():
				d[s[i]] += 1
			else:
				d[s[i]] = 1
		for i in d:
			sum += d[i] * (d[i] + 1) // 2
		return sum


class Solution:

	def countSubstringWithEqualEnds(self, s):
		c = 0
		p = 0
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
				c += d[i]
			else:
				d[i] = 1
				p += 1
		return c + p


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = {}
		rpt = 0
		uni = 0
		for i in s:
			if i in count:
				count[i] += 1
				rpt += count[i]
			else:
				uni += 1
				count[i] = 1
		return rpt + uni


class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		u = 0
		r = 0
		for i in s:
			if i not in h:
				h[i] = 1
				u += 1
			else:
				h[i] += 1
				r += h[i]
		return r + u


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		c = len(s)
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d.values():
			k = (i - 1) * i // 2
			c += k
		return c


class Solution:

	def countSubstringWithEqualEnds(self, s):
		maxlen = 0
		char_num = {}
		for i in range(0, len(s)):
			if s[i] in char_num:
				maxlen += char_num[s[i]]
				char_num[s[i]] += 1
			else:
				char_num[s[i]] = 1
		return maxlen + len(s)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = len(s)
		d = {}
		for i in range(len(s)):
			if s[i] in d:
				count += d[s[i]]
				d[s[i]] += 1
			else:
				d[s[i]] = 1
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		unq = 0
		rpt = 0
		for i in s:
			if i not in d:
				d[i] = 1
				unq += 1
			else:
				d[i] += 1
				rpt += d[i]
		return rpt + unq


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		c = 0
		for x in s:
			c += 1
			if d.get(x) is None:
				d[x] = -1
			d[x] += 1
		for x in d.values():
			c += int(x * (x + 1) / 2)
		return c


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		uni = 0
		rep = 0
		for i in s:
			if i not in d:
				d[i] = 1
				uni += 1
			else:
				d[i] += 1
				rep += d[i]
		return uni + rep


class Solution:

	def countSubstringWithEqualEnds(self, s):
		h = {}
		count = 0
		for ch in s:
			if ch not in h:
				h[ch] = 1
				count += 1
			else:
				h[ch] += 1
				count += h[ch]
		return count


class Solution:

	def countSubstringWithEqualEnds(self, s):
		letters = [0 for i in range(0, 26)]
		for i in s:
			letters[ord(i) - ord('a')] += 1
		cnt = 0
		for i in letters:
			cnt += i * (i + 1) // 2
		return cnt


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = dict()
		ans = 0
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 1
				ans += 1
			else:
				d[s[i]] += 1
				ans += d[s[i]]
		return ans


class Solution:

	def countSubstringWithEqualEnds(self, s):
		n = len(s)
		a = ''
		for i in s:
			if i not in a:
				a += i
		res = []
		for i in a:
			x = s.count(i)
			val = res.append(x * (x - 1) // 2)
		return sum(res) + n


class Solution:

	def countSubstringWithEqualEnds(self, s):
		l = len(s)
		x = []
		for i in s:
			if i not in x:
				x.append(i)
		d = []
		for i in x:
			y = s.count(i)
			d.append(int(y * (y - 1) / 2))
		return sum(d) + l


class Solution:

	def countSubstringWithEqualEnds(self, s):
		res = len(s)
		k = {}
		for i in s:
			if i in k.keys():
				k[i] += 1
			else:
				k[i] = 1
		for x in k.keys():
			if k[x] > 1:
				res += k[x] * (k[x] - 1) // 2
		return res


class Solution:

	def countSubstringWithEqualEnds(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		ans = 0
		for x in d:
			ans += d[x] * (d[x] + 1) // 2
		return ans


class Solution:

	def countSubstringWithEqualEnds(self, s):
		count = 0
		dict_main = {}
		for i in s:
			if i in dict_main.keys():
				dict_main[i] = dict_main[i] + 1
			else:
				dict_main[i] = 1
		for i in dict_main.keys():
			count += dict_main[i] * (dict_main[i] + 1) / 2
		return int(count)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)


from collections import Counter as C

class Solution:

	def countSubstringWithEqualEnds(self, s):
		z = 0
		for j in C(s).values():
			z += j * (j + 1) // 2
		return z
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		from collections import Counter
		dicta = Counter(s)
		add = sum([(x - 1) * x // 2 for (i, x) in dicta.items() if x > 1])
		return add + len(s)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		arr = [s[i] for i in range(len(s))]
		arr = list(set(arr))
		my_dic = {}
		for i in range(len(arr)):
			my_dic[arr[i]] = 0
		for i in range(len(s)):
			my_dic[s[i]] += 1
		ans = 0
		for x in my_dic:
			ans += int(my_dic[x] * (my_dic[x] + 1) / 2)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)


class Solution:

	def countSubstringWithEqualEnds(self, s):
		c = 0
		m = {}
		for i in s:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
			c += m[i]
		return c
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)


class Solution:

	def fact(self, k):
		prod = 1
		for itr in range(1, k + 1):
			prod *= itr
		return prod

	def c(self, n, r):
		return self.fact(n) / (self.fact(n - r) * self.fact(r))

	def countSubstringWithEqualEnds(self, s):
		lst = list(s)
		dic = {}
		count = 0
		for itr in range(len(lst)):
			if lst[itr] not in dic.keys():
				dic[lst[itr]] = 1
			else:
				dic[lst[itr]] += 1
		for itr in dic.values():
			if itr == 2:
				count += 1
			elif itr > 2:
				count += self.c(itr, 2)
		return int(count + len(s))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.countSubstringWithEqualEnds(s)
		print(answer)