Python: how to optimize

Question

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.

Wouldn't `abaca` give you *3*, not 1? `aba`, `aca` and `abaca` are all substrings with matching first and last character. — Martijn Pieters, Jun 20 '15 at 18:32
@ankitbiradar: but if `a` is 1, then `aba` gives 3 (the substrings `aba`, `a`, and `b` all qualify if strings of length one count), and `abaca` would be 6 (3 unique single characters plus the 3 substrings I already identified). — Martijn Pieters, Jun 20 '15 at 18:37
@KhalilAmmour-خليلعمور: not sure how you got 4 from `a`. — Martijn Pieters, Jun 20 '15 at 18:38
In "aba" you have 4 matches: "a", "b", "a", "aba". Do you want distinct substrings which are also palindromes? — Kenny Ostrom, Jun 20 '15 at 18:42
basically number of substrings with first and last character same and repetition of substrings allowed right? — Obscure Geek, Jun 20 '15 at 18:45

score 2 · Accepted Answer · edited Jun 20 '15 at 19:00

2

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.

edited Jun 20 '15 at 19:00

Obscure Geek

749
10
22

answered Jun 20 '15 at 18:40

JukesOnYou

263
2
10

1

Darn, I was going to say that, if his original problem turns out to match this. I am not clear yet on what he actually wants since the math doesn't work out with his examples. Actually your math doesn't work either at first glance although that's so hard to judge. It looks like you would fail on the first test case, f("a") == 1, because 1*0/2 = 0. Just add len(input)? – Kenny Ostrom Jun 20 '15 at 18:45
Its perfect. What I want to know is how did you come up with that logic, whats the thought process – Jun 20 '15 at 18:48
for f("aba") also how will this logic give ans 4? *b* count is one and *a* count is 2 i.e. (1*0/2) + (2*1/2) = 1. – Obscure Geek Jun 20 '15 at 18:51
Yep if substrings of length one are qualified just add length of the string to the answer that't it – JukesOnYou Jun 20 '15 at 18:54
Look at the use of defaultdict in this answer to handle the first part: http://stackoverflow.com/questions/991350/counting-repeated-characters-in-a-string-in-python – Kenny Ostrom Jun 20 '15 at 18:58
@ankrit, re: thought process. First eliminate the irrelevant stuff like raw_input and print. They should not be in the function, which takes a string and returns a number. But you asked for optimization, so the obvious place to start is eliminating the intermediate values. You don't care what the substrings are, so don't look at them at all; just look for repeated characters. From there it is simple combinatorics. – Kenny Ostrom Jun 20 '15 at 19:06

Python: how to optimize

1 Answers1