Find first repeated character in a string using Java

By Atul Rai | Last Updated: September 2, 2018 Previous       Next

This tutorial will help you to find the first recurring or repeated character in a given string. By asking these types of question interviewer want to know your logical ability and how efficiently you can do it.

Let’s see some sample examples.

• XYZAYB → In this string Y is the first recurring/repeated character.
• ABCDECD → In this string C is the first recurring/repeated character but we can see that D is also repeated. When we find a first recurring character we do not need to check the next.
• ABCD → Here there is NO character is repeated so we return null or any logical message.

1. Native Solution

In this solution, we pick up every character one by one and check is there any occurrence with subsequent character by character. If we find the recurring character we will return the character else move on the next character.

In this native solution, we are checking every potential pair of character in the string. And the number of the pair we need to check is O(n²) where n is the number of character in a string.

package org.websparrow;

public class FirstRecurringChar {

	public static void main(String[] args) {
		String str = "XYZAYB";
		char recurringChar = firstRecurringCharacter(str);

		if (recurringChar != 0) {
			System.out.println(recurringChar + " is first recurring character");
		} else {
			System.out.println("No recurring char");
		}
	}

	public static char firstRecurringCharacter(String str) {

		for (int i = 0; i < str.length(); i++) {

			char ch1 = str.charAt(i);

			for (int j = i + 1; j < str.length(); j++) {
				char ch2 = str.charAt(j);

				if (ch1 == ch2) {
					return ch1;
				}
			}
		}
		return 0;
	}
}

You will find the below result on your console log.

Y is first recurring character

2. Efficient Solution

We can find the more efficiently by using some data structure. In this example, we will store every character in HashSet and check if HashSet conations the next character if true return the same character.

For this solution, the time complexity is O(n) where n is the number of character in a string.

package org.websparrow;

import java.util.HashSet;
import java.util.Set;

public class FirstRecurringCharOptimized {

	public static void main(String[] args) {
		String str = "ABCDECD";
		char recurringChar = firstRecurringCharacter(str);

		if (recurringChar != 0) {
			System.out.println(recurringChar + " is first recurring character");
		} else {
			System.out.println("No recurring char");
		}
	}

	public static char firstRecurringCharacter(String str) {

		Set<Character> charSet = new HashSet<>();

		for (int i = 0; i < str.length(); i++) {

			char ch = str.charAt(i);

			if (charSet.contains(ch)) {
				return ch;
			} else {
				charSet.add(ch);
			}
		}
		return 0;
	}
}

You will find the below result on your console log.

C is first recurring character