Leetcode solution complexity - Longest substring without repeating element

Question

I have come up with a solution for the Leetcode probelm "Longest substring without repeating element" that is basically a brute force approach. For practice, I am also trying to find its complexity but would like to get some feedback on how to do it since I am not that great at that.

The solution code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ## Brute force approach
        if len(s) == 0:
            return 0
        orig_elts = [s[0]]
        pre_length = 1
        idx = 1

        while idx <= len(s) - 1:
            #print("This is idx", idx)
            if s[idx] not in orig_elts:
                orig_elts.append(s[idx])
                pre_length = max(pre_length, len(orig_elts))
                idx += 1
            else:
                pre_length = max(pre_length, len(orig_elts))
                tmp_idx = orig_elts.index(s[idx])
                orig_elts = orig_elts[tmp_idx + 1:]


        return pre_length

I believe the complexity is O(n^2) since for the while loop I am passing through the whole string once and that has complexity O(n) and then the operation of finding if s[idx] is in orig_elts takes O(n). So I was concluding the algorithm would have O(n^2) complexity.

Thanks for any feedback or suggestions on how to calculate this. This kind of question are not my strong suit and so I am trying to get as much practice as possible.

Answer 1

Yes, worst case complexity is O(n^2)