Remove Duplicate Characters
Problem
Read one word. Remove repeated characters and keep only the first occurrence of each character, in the original order.
Constraints
- 1 <= length <= 10^5, ASCII, no spaces
Examples
Input
programming
Output
progamin
Solutions
A set answers 'did I see this character before?' in constant time. We keep a character only the first time.
/*
* Problem : Process one line of text.
* Input : One line of text.
* Output : Unique characters in order.
* Approach: Use a set.
* Time : O(n)
* Space : O(k)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(String s) {
// Step 1: A set remembers the characters we have already seen.
java.util.Set<Character> seen = new java.util.HashSet<>();
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
// Step 2: add returns true only when the character is new.
if (seen.add(c)) {
// Step 3: Keep the first occurrence.
result.append(c);
}
}
return result.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(solve(s));
}
}
Hints (1)
- Which data structure remembers seen items?