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?

CodePudding user response：

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])