CODEWITHSUNDEEP
pythonlistpython-2.7
user4881368
user4881368

Reputation:

Python: how to optimize

Suppose I am given a string of len n, for every substring whose first and last characters are same I should add 1 to fx and print the final fx.

ex for "ababaca" , f("a")=1 , f("aba")=1 , f("abaca")=1, but f("ab")=0 

n = int(raw_input())
string = list(raw_input())
f = 0
for i in range(n):
    for j in range(n,i,-1):
        temp = string[i:j]
        if temp[0]==temp[-1]:
            f+=1
print f

Is there any way I can optimize my code for large strings as I am getting time out for many test cases.

Upvotes: 1

Views: 112

Answers (1)

JukesOnYou
JukesOnYou

Reputation: 263

You can just count the occurrences of each letter. For example, if there are n 'a's, in the string there will be n*(n-1)/2 substrings starting and ending with 'a'. You can do same for every letter, the solution is linear.

Add len(string) to the obtained value for final answer.

Upvotes: 2

Related Questions