CODEWITHSUNDEEP
pythonpython-3.x
Adakip
Adakip

Reputation: 21

Time Complexity of Leetcode 387

I need to have a better understanding of time complexity, this particular example seems to be confusing me.

Problem: (Source LeetCode) Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Based on my solution, i know that the for loop will iterate through the string worse case O(n) time, n being the length of the string. However inside the for loop im checking the count of each character and i know the count() method itself requires O(n) time. So making this a O(n^2) solution? Do i have that logic correct?

My Solution:

class Solution:
    def firstUniqChar(self, s: str) -> int:
       
        if len(s) == 0:
            return -1
        for char in range(len(s)):
            if s.count(s[char]) > 1:
                pass
            else: 
                return(char)
        return(-1)

So my code works for smaller test cases, however when testing a case where s is a huge string, it says time limit exceeded. I do not need solutions for the problem rather i just want to know if O(n^2) is the actual time complexity for my code.

Upvotes: 2

Views: 73

Answers (1)

Cireo
Cireo

Reputation: 4427

Yes, that is correct. The complexity of for ... len(s) is O(|s|), and so is s.count. Since you nested them, then you have O(|s|^2)

Upvotes: 3

Related Questions