CODEWITHSUNDEEP
pythondata-structurestime-complexity
Akanksha
Akanksha

Reputation: 51

What is the time complexity of these two solutions?

I am solving this problem: Palindromic Substrings.

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

I have tried multiple approaches and according to me both these approach have a complexity of O(N*3). But leetcode accepts one solution and return time limit exceeded for the other one.

Solution which is accepted:

def countSubstrings(self, s):
        count = len(s)
        for i in range(2, len(s)+1):
            j = 0
            while(j < len(s) and j+i <= len(s)):
                t = s[j:j+i]
                j = j + 1
                reverse_t = t[::-1]
                if t == reverse_t:
                    count += 1
        return count

Solution for which I get time limit exceeded

def countSubstrings(self, s):
        count = len(s)
        for i in range(2, len(s)+1):
            j = 0
            while(j < len(s) and j+i <= len(s)):
                t = s[j:j+i]
                j = j + 1
                reverse_t = ''
                for k in range(len(t)-1, -1, -1):
                    reverse_t += t[k]
                if t == reverse_t:
                    count += 1
        return count

The only change in these two algorithm is in one in my using Python slice to reverse the string and in the second when I am using a for loop. The time complexity for slice is O(K) where k is length of slice

Upvotes: 0

Views: 106

Answers (1)

Paritosh Singh
Paritosh Singh

Reputation: 6246

You wrote:

reverse_t = ''
for k in range(len(t)-1, -1, -1):
    reverse_t += t[k]

Because strings are immutable, constructing strings by adding 1 letter at a time is horribly inefficient, because on each iteration, you have to construct an entirely new object. Essentially, it's the string concatenation that you didn't account for in your calculation. constructing a string of length n letter by letter is effectively o(n**2)

To demonstrate how much of a difference this can make, here is a simple setup:

def letter_by_letter_reverse(string):
    reverse_t = ''
    for k in range(len(string)-1, -1, -1):
        reverse_t += string[k]
    return reverse_t

def slice_reverse(string):
    reverse_t = string[::-1]
    return reverse_t

test = 'some_string' * 500

%timeit letter_by_letter_reverse(test)
#1.44 ms ± 204 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit slice_reverse(test)
#8.2 µs ± 56.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Upvotes: 2

Related Questions