Here is the solution as I would write it for a coding interview:
Quick, easy, and clean (at least in my opinion)
Time complexity is O(n).
Justification: We loop through each letter in the
String exactly once (and only perform O(1) operations on it, which is the HashSet's add). Therefore the algorithm is T(n) where n = length of String, in the best and worst case, therefore it is O(n).
Space complexity is O(n).
Justification is easiest through examples.
Take the worst case. String "aabbcc". This would result in duplicates holding "A", "B", "C", and allCharactersSet holding "A", "B", "C", therefore worst case is T(n * 2)
Take the best case. String "aaaaa". This would result in duplicates holding "A", and allCharactersSet holding "A", therefore best case is T(1)
Average case would be T(n), you can work out example "abc" to see why.
Because the worst case is n times a constant, this is linear, and therefore the space complexity is O(n).