Problem Statement:You are given a function \$f(x)\$, where \$f(x)\$ is \$1\$ if the first and last characters of string \$x\$ are equal; else it is \$0\$.   You are given a string \$S\$ and you have to find the sum of \$f(x)\$ for all substrings \$x\$ of given string \$S\$.Sample Input:7ababacaSample Output:14Explanation: f(a)=1, f(aba)=1, f(abaca)=1 but f(ab)=0, f(bac)=0. Hence counting all substrings we get 14.The 14 substring are a - 4(times) b - 2 c - 1 aba - 2 bab - 1 aca - 1 ababa - 1 abaca - 1 ababaca - 1My code:l = int(input())s = [x for x in input().strip()]print(l + sum([1 for i in range(0,l-1) for j in range(i+1,l) if s[i] == s[j]]))I have tried the following snippets too:Timeout:from collections import Counterimport mathl, s = int(input()), [x for x in input()]print(l + sum([math.factorial(value-1) for value in Counter(s).values() if value != 1]))Wrong answer:import itertoolsl, s = int(input()), input()print(sum(int(i[0] == i[-1]) for i in itertools.combinations_with_replacement(s,2)))The solutions is working fine except that it times out in certain test cases. Can anyone suggest a better way to do this?
Number of sub strings with same first and last character
python;performance;strings;programming challenge;python 3.x
After numerous suggestions on this portal and a good night's sleep, I could come up with this :)from collections import Counter_, s = int(input()), input()occurences = Counter(s).values()print(sum(n*(n+1)//2 for n in occurences))And it works! :D