Backend interview prep

Start Learning

Remove Duplicate Characters

Java coding interview problem for String Coding: Remove Duplicate Characters.

Removing duplicate characters from a string is one of the most frequently asked Java String interview problems.

Although the problem looks simple, it tests several important programming concepts, including:

  • String Traversal
  • Character Processing
  • Collections Framework
  • HashSet
  • LinkedHashSet
  • StringBuilder
  • Time Complexity
  • Space Optimization

Interviewers often ask this question in different forms, such as:

  • Remove duplicate characters while preserving order.
  • Remove duplicates without using Collections.
  • Remove duplicate words instead of characters.
  • Count duplicate characters.
  • Find the first non-repeating character.

Learning multiple approaches prepares you for all these interview variations.

Problem Statement

Given a string, remove all duplicate characters while preserving the order of their first occurrence.

Return the resulting string.

Example 1

Input

programming

Output

progamin

Explanation

Duplicate characters:

r

g

m

Only their first occurrence is kept.

Example 2

Input

banana

Output

ban

Example 3

Input

aaaaaa

Output

a

Example 4

Input

Hello World

Output

Helo Wrd

What are Duplicate Characters?

Duplicate characters are characters that appear more than once in a string.

Example

banana

Characters

b a n a n a

Duplicate characters

a

n

Unique characters

b

a

n

Result

ban

Another Example

Input

programming

Unique characters

p

r

o

g

a

m

i

n

Output

progamin

Why is this Question Asked in Interviews?

Interviewers use this problem to evaluate whether candidates understand:

  • Character traversal
  • Nested loops
  • Collections Framework
  • HashSet
  • LinkedHashSet
  • StringBuilder
  • Time Complexity
  • Space Optimization

It is also the foundation for many advanced interview questions.

Examples include:

  • Count Duplicate Characters
  • First Non-Repeating Character
  • Character Frequency
  • Remove Duplicate Words
  • Longest Substring Without Repeating Characters

Real-World Applications

Removing duplicate characters has several practical applications.

Data Cleaning

Duplicate characters are removed during text normalization.

Search Engines

Search systems normalize user input before indexing.

Password Validation

Repeated characters may be analyzed while checking password strength.

Text Editors

Editors eliminate duplicate characters during formatting.

Data Compression

Compression algorithms remove repeated patterns before encoding.

Understanding Character Uniqueness in Java

Consider the following string.

String input = "banana";

Memory representation

+---+---+---+---+---+---+
| b | a | n | a | n | a |
+---+---+---+---+---+---+
 0   1   2   3   4   5

While traversing the string:

  • b appears for the first time.
  • a appears for the first time.
  • n appears for the first time.
  • The second a is a duplicate.
  • The second n is a duplicate.
  • The third a is a duplicate.

Final Result

ban

HashSet vs LinkedHashSet

This is a common interview discussion.

HashSet

  • Stores only unique elements.
  • Does not preserve insertion order.

Example

Input

banana

Possible Output

nab

The order is not guaranteed.

LinkedHashSet

  • Stores unique elements.
  • Preserves insertion order.

Input

banana

Output

ban

This makes LinkedHashSet the preferred choice for this problem.

Mathematical Concept

Suppose

APPLE

Traversal

A

↓

P

↓

P

↓

L

↓

E

Visited Characters

A

↓

A P

↓

A P

↓

A P L

↓

A P L E

Final Output

APLE

Visual Representation

Input

PROGRAM

Traversal

P ✓

R ✓

O ✓

G ✓

R ✗

A ✓

M ✓

Output

PROGRAM

↓

PROGAM

Dry Run

Input

banana

Initially

Visited = {}

Result = ""

Iteration 1

Character

b

Not visited.

Visited

{b}

Result

b

Iteration 2

Character

a

Visited

{b, a}

Result

ba

Iteration 3

Character

n

Visited

{b, a, n}

Result

ban

Iteration 4

Character

a

Already visited.

Skip.

Iteration 5

Character

n

Already visited.

Skip.

Iteration 6

Character

a

Already visited.

Skip.

Final Output

ban

Approach 1 — Using LinkedHashSet (Recommended)

The easiest and most interview-friendly solution is to use a LinkedHashSet.

Why?

Because it:

  • Stores only unique characters.
  • Preserves insertion order.
  • Automatically ignores duplicates.

Algorithm

  1. Create a LinkedHashSet.
  2. Traverse every character.
  3. Add each character into the set.
  4. Duplicate characters are ignored automatically.
  5. Traverse the set.
  6. Build the result string.

Java Program

import java.util.LinkedHashSet;

public class RemoveDuplicateCharacters {

    public static String removeDuplicates(String input) {

        LinkedHashSet<Character> set = new LinkedHashSet<>();

        for (char ch : input.toCharArray()) {
            set.add(ch);
        }

        StringBuilder result = new StringBuilder();

        for (char ch : set) {
            result.append(ch);
        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(removeDuplicates("programming"));

        System.out.println(removeDuplicates("banana"));

    }

}

Output

progamin

ban

Step-by-Step Code Explanation

Create a LinkedHashSet.

LinkedHashSet<Character> set = new LinkedHashSet<>();

Traverse the string.

for (char ch : input.toCharArray())

Insert every character.

set.add(ch);

Duplicate values are ignored automatically.

Create a StringBuilder.

StringBuilder result = new StringBuilder();

Append every unique character.

result.append(ch);

Return the final string.

return result.toString();

Dry Run of LinkedHashSet

Input

APPLE
Iteration Character Set Result
1 A A A
2 P A P AP
3 P A P AP
4 L A P L APL
5 E A P L E APLE

Output

APLE

Advantages

  • Very easy to implement.
  • Preserves insertion order.
  • Automatically removes duplicates.
  • Excellent readability.
  • Common production solution.

Drawbacks

  • Requires additional memory.
  • Uses Java Collections.
  • Some interviewers may ask for a solution without using a Set.

Approach 2 — Using StringBuilder and indexOf()

Another interview-friendly solution avoids using any Collection classes.

The idea is simple:

  • Traverse the string.
  • Check whether the character already exists in the result.
  • If not, append it.

Algorithm

  1. Create an empty StringBuilder.
  2. Traverse every character.
  3. Check whether the character already exists using indexOf().
  4. If it does not exist, append it.
  5. Return the final string.

Java Program

public class RemoveDuplicatesStringBuilder {

    public static String removeDuplicates(String input) {

        StringBuilder result = new StringBuilder();

        for (char ch : input.toCharArray()) {

            if (result.indexOf(String.valueOf(ch)) == -1) {
                result.append(ch);
            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(removeDuplicates("banana"));

        System.out.println(removeDuplicates("programming"));

    }

}

Output

ban

progamin

Step-by-Step Code Explanation

Create an empty result.

StringBuilder result = new StringBuilder();

Traverse every character.

for (char ch : input.toCharArray())

Search for the character.

result.indexOf(String.valueOf(ch))

If it returns

-1

the character has not been added yet.

Append the unique character.

result.append(ch);

Return the result.

return result.toString();

Time & Space Complexity

Approach Time Extra Space
LinkedHashSet O(n) O(n)
StringBuilder + indexOf() O(n²) O(n)

Where:

  • n = length of the input string.

The StringBuilder + indexOf() approach performs a search for each character, resulting in quadratic time complexity in the worst case.

Comparison of Approaches

Feature LinkedHashSet StringBuilder + indexOf()
Interview Friendly ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Preserves Order ✅ ✅
Collections Required ✅ ❌
Time Complexity O(n) O(n²)

Advantages

  • Both approaches preserve the original character order.
  • LinkedHashSet provides excellent performance with clean code.
  • StringBuilder + indexOf() avoids using Collection classes.
  • Both solutions are suitable for most practical string-processing tasks.

Drawbacks

  • LinkedHashSet requires additional memory.
  • StringBuilder + indexOf() becomes inefficient for large strings because of repeated searches.
  • Neither approach is optimized specifically for ASCII-only input.

In Part 2, we'll cover:

  • Approach 3 – Using Boolean Array (ASCII Optimization)
  • Approach 4 – Using Java Streams (Java 8+)
  • Approach 5 – Using HashMap
  • Remove Duplicate Words from a Sentence
  • Preserve Original Character Order
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Frequently Asked Interview Questions
  • Interview Tips

Approach 3 — Using Boolean Array (ASCII Optimization)

If the input contains only ASCII characters, we can optimize the solution using a boolean array.

Each array index represents one ASCII character.

Since ASCII contains 128 standard characters (or 256 extended ASCII characters), checking duplicates becomes very fast.

Algorithm

  1. Create a boolean array.
  2. Traverse each character.
  3. If the character has not been seen before:
    • Mark it as visited.
    • Append it to the result.
  4. Return the final string.

Java Program

public class RemoveDuplicatesBooleanArray {

    public static String removeDuplicates(String input) {

        boolean[] visited = new boolean[256];

        StringBuilder result = new StringBuilder();

        for (char ch : input.toCharArray()) {

            if (!visited[ch]) {
                visited[ch] = true;
                result.append(ch);
            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(removeDuplicates("banana"));

        System.out.println(removeDuplicates("programming"));

    }

}

Output

ban

progamin

Dry Run

Input

APPLE

Initially

visited[] = false

Result = ""
Iteration Character Visited? Result
1 A No A
2 P No AP
3 P Yes AP
4 L No APL
5 E No APLE

Output

APLE

Advantages

  • Extremely fast.
  • Constant-time lookup.
  • Simple implementation.
  • Excellent for ASCII input.

Drawbacks

  • Works only for ASCII efficiently.
  • Not suitable for all Unicode characters.
  • Requires additional memory for the lookup array.

Approach 4 — Using Java Streams (Java 8+)

Java Streams provide a concise and modern way to remove duplicate characters.

The distinct() operation automatically removes duplicates while preserving encounter order.

Algorithm

  1. Convert the string into a stream of characters.
  2. Apply distinct().
  3. Collect the characters into a string.

Java Program

import java.util.stream.Collectors;

public class RemoveDuplicatesStreams {

    public static String removeDuplicates(String input) {

        return input.chars()
                .mapToObj(ch -> String.valueOf((char) ch))
                .distinct()
                .collect(Collectors.joining());

    }

    public static void main(String[] args) {

        System.out.println(removeDuplicates("banana"));

    }

}

Output

ban

Advantages

  • Very concise.
  • Modern Java style.
  • Easy to read.
  • Preserves character order.

Drawbacks

  • Slightly slower than loop-based solutions.
  • Stream overhead.
  • Usually not preferred in coding interviews.

Approach 5 — Using HashMap

Instead of storing only unique characters, we can store every visited character inside a HashMap.

The map key represents the character.

The value indicates whether it has already been processed.

Algorithm

  1. Create a HashMap.
  2. Traverse each character.
  3. If it is not present in the map:
    • Add it.
    • Append it to the result.
  4. Return the final string.

Java Program

import java.util.HashMap;

public class RemoveDuplicatesHashMap {

    public static String removeDuplicates(String input) {

        HashMap<Character, Boolean> map = new HashMap<>();

        StringBuilder result = new StringBuilder();

        for (char ch : input.toCharArray()) {

            if (!map.containsKey(ch)) {

                map.put(ch, true);

                result.append(ch);

            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        System.out.println(removeDuplicates("programming"));

    }

}

Output

progamin

Advantages

  • Easy to extend for frequency counting.
  • Flexible implementation.
  • Good when additional metadata is needed.

Drawbacks

  • Uses more memory than HashSet.
  • Slightly more verbose.

Remove Duplicate Words from a Sentence

Interviewers sometimes modify the problem:

Remove duplicate words instead of characters.

Example

Input

Java is Java is awesome

Output

Java is awesome

Java Program

import java.util.LinkedHashSet;

public class RemoveDuplicateWords {

    public static void main(String[] args) {

        String sentence = "Java is Java is awesome";

        String[] words = sentence.split(" ");

        LinkedHashSet<String> set = new LinkedHashSet<>();

        for (String word : words) {
            set.add(word);
        }

        System.out.println(String.join(" ", set));

    }

}

Output

Java is awesome

Preserve Original Character Order

One of the most common interview questions is:

Can you remove duplicates while preserving the original order?

Example

Input

mississippi

Output

misp

Notice

The first occurrence of every character is preserved.

Order

m

i

s

p

This is why LinkedHashSet is generally preferred over HashSet.

Unicode Considerations

Java stores text using Unicode.

Examples

こんにちは

नमस्ते

😊😊🚀🚀

The Boolean Array solution assumes ASCII characters.

For applications that process international text, prefer:

  • LinkedHashSet<Character>
  • HashMap<Character, Boolean>

If your application must correctly process supplementary Unicode characters (such as many emoji), consider iterating over Unicode code points instead of individual char values.

Edge Cases

Input Expected Output
"" ""
"a" "a"
"aaaa" "a"
"abcdef" "abcdef"
"112233" "123"
"Hello World" Helo Wrd
null Handle appropriately based on application requirements

Time & Space Complexity

Approach Time Extra Space
LinkedHashSet O(n) O(n)
StringBuilder + indexOf() O(n²) O(n)
Boolean Array O(n) O(1)*
Java Streams O(n) O(n)
HashMap O(n) O(n)

Note: The Boolean Array uses a fixed-size lookup table (for example, 256 entries for extended ASCII), so its extra space is considered O(1) with respect to the input size.

Comparison of All Approaches

Approach Interview Friendly Performance Order Preserved
LinkedHashSet ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ✅
StringBuilder + indexOf() ⭐⭐⭐⭐ ⭐⭐⭐ ✅
Boolean Array ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ✅
Java Streams ⭐⭐⭐ ⭐⭐⭐ ✅
HashMap ⭐⭐⭐⭐ ⭐⭐⭐⭐ ✅

Common Interview Mistakes

Mistake 1

Using HashSet instead of LinkedHashSet.

Wrong

banana

↓

nab

Order is not guaranteed.

Correct

banana

↓

ban

Mistake 2

Using string concatenation inside a loop.

Wrong

result = result + ch;

Better

StringBuilder result = new StringBuilder();

Mistake 3

Ignoring uppercase and lowercase differences.

Example

AaBb

Should A and a be treated as the same character?

Clarify the requirement before coding.

Mistake 4

Using the Boolean Array approach for full Unicode input.

The array approach is intended for ASCII-based solutions.

Mistake 5

Not handling empty strings.

Input

""

Output

""

Always test edge cases.

Interview Follow-up Questions

Q1. Remove duplicate characters without using Collections.

Q2. Remove duplicate words from a sentence.

Q3. Count duplicate characters.

Q4. Find the first non-repeating character.

Q5. Which approach is the most efficient?

Q6. How would you support Unicode?

Q7. Can you preserve the original order?

Q8. What is the time complexity?

Q9. How would you remove duplicates in a character array?

Q10. How would you remove duplicates from a stream of characters?

Related Problems

  • Count Duplicate Characters
  • Character Frequency
  • First Non-Repeating Character
  • Longest Substring Without Repeating Characters
  • Remove Duplicate Words
  • Reverse String
  • Palindrome String
  • Group Anagrams
  • Valid Anagram

Key Takeaways

  • Removing duplicate characters is a classic Java String interview problem.
  • LinkedHashSet is the most practical solution because it removes duplicates while preserving insertion order.
  • A Boolean Array provides the fastest solution for ASCII input.
  • Java Streams offer a concise functional programming approach but introduce additional overhead.
  • HashMap is useful when duplicate removal is combined with frequency counting or other metadata.
  • Always clarify whether character order must be preserved and whether the input is limited to ASCII or includes full Unicode.

Frequently Asked Interview Questions

Q1. Why is LinkedHashSet preferred over HashSet?

LinkedHashSet preserves the insertion order of elements while ensuring uniqueness.

Example

Input

banana

Output

ban

A HashSet does not guarantee this order.

Q2. Which approach performs the best?

For ASCII input, the Boolean Array solution provides the best performance with O(n) time and constant extra space.

For general Java applications, LinkedHashSet is usually the best balance of simplicity and efficiency.

Q3. Can duplicate removal be performed without Collections?

Yes.

A common interview solution uses StringBuilder together with indexOf() to check whether a character has already been added.

Q4. Why use StringBuilder instead of string concatenation?

Repeated string concatenation creates many intermediate String objects because strings are immutable.

StringBuilder is more memory-efficient and performs better inside loops.

Q5. How would you count duplicate character frequencies?

Use a HashMap<Character, Integer>.

Example

programming

↓

p → 1
r → 2
o → 1
g → 2
a → 1
m → 2
i → 1
n → 1

This is a common follow-up interview question.

Interview Tip

If an interviewer asks:

"Remove duplicate characters from a string while preserving the order."

Start with the LinkedHashSet approach because it is clean, efficient, and demonstrates knowledge of the Java Collections Framework.

Then discuss alternative solutions:

  1. LinkedHashSet for general-purpose Java applications.
  2. Boolean Array for ASCII-only optimization.
  3. StringBuilder + indexOf() when Collections are not allowed.
  4. Java Streams for Java 8+ functional programming.
  5. HashMap when duplicate removal needs to be combined with character frequency counting.

Explaining the trade-offs between these approaches demonstrates strong problem-solving skills and a solid understanding of Java data structures and algorithms.