Remove Duplicates From String
You are given a string (STR) of length N, consisting of only the lower case English alphabet.

Your task is to remove all the duplicate occurrences of characters in the string.

For Example:

If the given string is: abcadeecfb Then after deleting all duplicate occurrences, the string looks like this: abcdef

Input Format:

The only input line contains a string (STR).

Output Format:

Print the string after removing all the duplicate occurrences.

Constraints:

1

Question

Remove Duplicates From String

You are given a string (STR) of length N, consisting of only the lower case English alphabet.

Your task is to remove all the duplicate occurrences of characters in the string.

For Example:

If the given string is:
abcadeecfb

Then after deleting all duplicate occurrences, the string looks like this:
abcdef

Input Format:

The only input line contains a string (STR).

Output Format:

Print the string after removing all the duplicate occurrences.

Constraints:

1 <= N <= 4*10^5

Time Limit: 1sec

Accepted Answer

I used the concept of sets to solve this
All 10 test cases passed

Accepted Answer

Brute Force Approach

Iterate for each character of the string. For each index, we run another loop starting from the beginning of the string upto that index, and check whether that character has occurred before. If so, we do not include this character in the final string.

Space Complexity: O(1)Explanation:

O(1)

Since we using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the length of the string.

Traversing the string once takes O(N) time, and for each index we run another traversal, making it of the order O(N ^ 2).

Accepted Answer

Tree Set / BST Approach

We maintain a self-balancing BST/TreeSet to keep track of all previously encountered characters.

Now, as we traverse the string, for each index, we check whether that character is present in the BST/TreeSet.

If so, we do not include it in the final string.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string.

Since we are using a set consisting of maximum 26 characters.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the string.

Traversing the string once takes O(N) time, and for each index, insertion and retrieval of characters take O(log(26)) time at maximum, which is considered constant.

Accepted Answer

Unordered Map / Set Approach

We can maintain a 26 sized array to keep track of whether a character has previously occurred in the string or not since it is mentioned that we will encounter only lower case characters.

Alternately, we can use either a hashmap, hashset or dictionary as well. keep track whether a character has previously occurred in the string or not.

This makes our updates and lookups much faster.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string.

Since we are using an array to store a maximum of 26 characters

Time Complexity: O(n)Explanation:

O(N), where N is the length of the string.

Traversing the string once takes O(N) time, and for each index, update and lookup operations of characters take O(1) time.

You are given a string (STR) of length N, consisting of only the lower case English alphabet.

Your task is to remove all the duplicate occurrences of characters in the string.

For Example:

Input Format:

Output Format:

Constraints:

Top Cvent Software Developer interview questions & answers

Popular interview questions of Software Developer