CODEWITHSUNDEEP
stringpython-3.xpython-2.7substring
Mansour Zayer
Mansour Zayer

Reputation: 384

Hackerrank `super-functional-strings` terminates due to timeout

Given a string, p, consisting of lowercase letters, compute the summation of function F(p) = [len(p)**distinct(p)]%[10**9 + 7] over all possible distinct substrings of F. As the result is quite large, print it modulo 10**9 + 7.

For example for 'aba' it is:

For which the sum equals 19.

The following is my solution:

import os
import sys

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    for j in range(length):
        for i in range(j+1, length):
            b = s[j:i]
            if b not in a:
                a.append(b)
                thesum += (len(b)**len(set(b)))%(modu)
    summ = thesum%(modu)       
    return(summ)

What can I do to optimize it so that timeout won't occur? (I'm guessing external libraries is not allowed)

Upvotes: 2

Views: 976

Answers (2)

Josh Dawson
Josh Dawson

Reputation: 25

One change that would remove an O(n) factor of complexity would be to make a a set instead of a list.

To compute b in a for a list requires searching through the whole list, O(n). Alternatively, computing b in a for a set is hashed which takes O(1).

Upvotes: 1

scnerd
scnerd

Reputation: 6103

You say "distinct substrings", so for starters use a set instead of a list so that duplicate substrings don't get stored and so that you get O(1) lookup time. Also, you don't need the modulo until the end, and Python supports addition of arbitrarily large integers, so you don't necessarily need the modulo inside your loop. Finally, I'd try this using comprehensions so that Python can loop faster. Here's what those recommendations leave you with:

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    substrs = {s[j:i] for j in range(length) for i in range(j+1, length)}
    return sum(len(b) ** len(set(b)) for b in substrs) % modu

I'm getting ~15-20x speedup by taking this approach.

Upvotes: 1

Related Questions