Remove Duplicates

Given a string str without spaces, the task is to remove all duplicate characters from it, keeping only the first occurrence.

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

Examples :

Input: str = "zvvo"
Output: "zvo"
Explanation: Only keep the first occurrence

Input: str = "gfg"
Output: "gf"
Explanation: Only keep the first occurrence

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= |str| <= 10⁵
str contains lowercase English alphabets

Approach 01

#include <string>
#include <unordered_set>

class Solution {
public:
    std::string removeDups(const std::string& str) {
        std::string result;
        std::unordered_set<char> seen; // To keep track of seen characters

        for (char ch : str) {
            if (seen.find(ch) != seen.end()) {
                continue; // If character is already seen, skip it
            }
            seen.insert(ch); // Mark the character as seen
            result += ch; // Append the character to result
        }

        return result;
    }
};

class Solution:
    def removeDups(self, s: str) -> str:
        result = ''
        seen = set()  # To keep track of seen characters

        for ch in s:
            if ch in seen:
                continue  # If character is already seen, skip it
            seen.add(ch)  # Mark the character as seen
            result += ch  # Append the character to result

        return result

Time Complexity

• Iteration Over Input String:

  Iterating over each character of the input string takes \( O(n) \) time, where n is the length of the input string str.

• Checking and Inserting in Unordered Set:

  Both the check (seen.find(ch)) and the insert (seen.insert(ch)) operations on the unordered set take average \( O(1) \) time due to the underlying hash table implementation.

• Overall Time Complexity:

  Since we perform \( O(1) \) operations for each of the \( n \) characters in the input string, the overall time complexity is \( O(n) \).

Space Complexity

• Unordered Set:

  The unordered set seen can contain at most all unique characters from the input string. In the worst case, it can contain \( O(n) \) elements, where n is the length of the input string.

• Result String:

  The result string result will store each unique character from the input string, leading to a space complexity of \( O(n) \) in the worst case.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the unordered set and the result string.