Space complexity of first non-repeating character algorithm

Question

The following algorithm I wrote finds the first non-repeating character in a string and returns its index or -1 if there are none:

def firstNonRepeatingCharacter(string):
    stack = []
    repeats = []
    for char in string:
        if char in stack:
            del stack[stack.index(char)]
            repeats.append(char)
        elif char not in stack and char not in repeats:
            stack.append(char)
    if len(stack) > 0:
        return string.index(stack[0])
    return -1

Would its space complexity be O(1) since you can have O(26) elements in either the stack or repeat lists, but not both?

Answer 1

Yes, additional space complexity consumed by your program is O(1), because data structures can include at most 26 elements regardless of the input size.
And again, your time complexity will be O(n), not O(n^2) due to the inner loops.

for char in string:   # O(n) - n being the number of characters in your string
   if char in stack:  # O(1) since stack can have at most 26 characters
      del stack[stack.index(char)] 
      repeats.append(char)
   elif char not in stack and char not in repeats:  # O(1) since stack and repeats can have at most 26 characters
      stack.append(char)
   if len(stack) > 0:
      return string.index(stack[0])

As stated in the comment, your variable named as stack is not actually a stack and some of the operations seem redundant. You can implement the same process more efficiently using a dict.

def firstNonRepeatingCharacter(string):
    dict_ = {}
    for idx in range(len(string)):   # n many iterations
        char = string.lower()[idx]
        dict_[char] = len(string) if (char in dict_) else idx
    
    idx = min(dict_.values()) # dict_ can have at most 26 elements - O(1)
    return -1 if(idx == len(string)) else idx

firstNonRepeatingCharacter("aabc")

Remember that x in dict operation takes O(1) in average due to the hash function used. Also length of the dictionary can be at most 26, number of characters in the alphabet.