Remove Duplicates From String

Moderate

0/80

Average time to solve is 25m

Contributed by

27 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

abcadeecfb

Sample Output 1:

abcdef

Sample Input 2:

zzzzzxx

Sample Output 2:

zx

Hint 1

Hint 2

Hint 3

Think of the easiest method to check whether a character has previously occurred in the string.

Approaches (3)

Approach 1

Approach 2

Approach 3

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.

Time Complexity

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

Space Complexity

O(1)

Since we using constant extra space.

(100% EXP penalty)

Remove Duplicates From String

Console