Given a string without spaces, the task is to remove duplicates from it.

Note: The original order of characters must be kept the same.

Example:

Input: S = "zvvo"
Output: "zvo"

Explanation: only keep the first occurrence

I've written the following code, and I want to know its Space complexity.

public class Solution {
    public String removeDups(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i< s.length(); i  ){
            String ch = Character.toString(s.charAt(i));
            if (sb.indexOf(ch) == -1)
                sb.append(ch);
        }
        return sb.toString();
    }
}

CodePudding user response：

Space complexity of your solution is O(n) since it requires allocating in memory an instance of StringBuilder which would contain up to n characters, and transforming it into a String of the same length.

These memory costs are fine, but time complexity of your solution can be improved. Presented code runs in O(n^2) because method indexOf() performs iteration over the characters in your StringBuilder instance under the hood, and it's being invoked for every character in the given string.

To reduce the time complexity you can maintain a HashSet, and offer each character to the Set, if the character gets rejected it would mean that it was encountered before.

Here's how it might be implemented:

public String removeDups(String s) {
    Set<Character> seen = new HashSet<>();
    StringBuilder sb = new StringBuilder();
    
    for (int i = 0; i < s.length(); i  ) {
        char ch = s.charAt(i);
        if (seen.add(ch)) sb.append(ch);
    }
    return sb.toString();
}

Although we are using some additional memory, space complexity remains the same O(n) (because constants are not taken into consideration while evaluating the algorithm's complexity, 2*n and 3*n would result in O(n)). And time complexity would be linear O(n).