How to find first recurring or duplicate character in given String? [Solved]

Hello guys, while surfing the Internet for a couple of weeks back, I come to know that this problem was asked on Google interviews, find the first recurring character in a given String. I don't know if that's true but this looks like a very simple coding problem from Google's Interview standard. If it was indeed asked, then that guy must have been very lucky. Anyway, I liked this coding problem and thought to write about it, because it's a good coding problem to check candidates' data structure and algorithms skills because it's tricky. It's tricky because it's very easy to make a mistake assuming just one recurring character in String, which you should avoid. Even if it was not asked on Google, you will potentially find this problem on various startups, and other IT companies like Infosys, TCS, Cognizant, Microsoft, and maybe Amazon. 

Looking from the other side of the table, I mean as an interviewer,  this is potentially a good coding problem to ask on telephonic tech interviews because there are multiple solutions to this problem and it also demonstrates how using the right data structure can improve your algorithm and performance.

Problem - Given a String, find the first recurring or duplicate character? Write a program to solve it, if there is no recurring character, just return null.

Example - If given String is :

"ABCDAB" - first recurring character is A

"ABBCDA" - first recurring or duplicate character is B

"ABCDA" - there is no recurring character, so your function should return null.

So, what are we waiting for, let's solve this Google Interview question and learn something new today? 

3 Ways to find first recurring character in given String

There are a couple of ways to solve this problem, but first, let's take a look at the simplest solution which doesn't involve any data structure or additional memory.

1. Brute force solution (Tricky)

The brute force or most intuitive way to solve this problem is to take one character at a time, starting from the first character, and then compare with all the characters, if it matches, then it's the first recurring character. Just return the character and you are done.

For example, if the input string is "ABCDAB" then there are two duplicate characters in it but "A" is the first recurring character. If you start with the letter "A" and compare it with "B", "C", "D", "A", you will find it matches with the last "A", hence this is the first recurring character.

You are not done yet, this is the place where most programmers make mistakes particularly beginners and careless programmers. This solution will work if there is just one recurring character in the String but it will not work if your string has more than one recurring character like in this case.

Instead of returning the character and exiting the function, you need to store this letter and its matching index into a variable, like firstRecurringCharacter="A", firstRecurringIndex="4".

Now, you will start with "B" and complete the iteration, this time, you will find the recurring character at index=5. 

Now, you need to compare and see if this next index is lower than the previous index, if yes, then swap and it will be the new first recurring character because it's observed first in the String. Once you complete with all characters, you will have your answer in variable "firstRecurringCharacter".

This solution doesn't use any additional memory but the time complexity of the solution is O(n^2) because you need to compare each character with everyone else. The first pass takes n comparison, the second pass takes n-1 comparison, third takes n-2, which means total N(N-1)/2 = O(n^2)

So, it works but it's not really the most efficient solution and let's see if we can improve it.

2. Using a Map, hash table, or Dictionary

Now, we are using a data structure called Map, or hash table, or dictionary in Python to improve our solution. In this solution, we go through all characters one by one and store them in the hash table as key and value as 1 to indicate that we have seen this character before. 

By default, the key and value will be null for an unseen character. When you hit a recurring character, you will find that it's already present on the map. At that point, you can stop processing and return that character. Done.

The time complexity of this solution is O(n) because we are just visiting each character one time. If there is n character in String then we will call the put() method N times. Since the time complexity of storing a key-value pair in the hash table is O(1), the time complexity of our solution would be O(n)* O(1) = O(n).

This means a much better solution than the previous one. It will take additional memory of O(n) because we need to store each character into the hash table but time has been reduced quite a lot. 

This is a good example of how using a data structure can improve performance and simplify an algorithm. It is also a good example of the space vs time tradeoff because we spend O(n) space to reduce time complexity from O(N^2) to O(n). By the way, if you are new to time and space complexity, you can check out these data structures and algorithms courses to learn and refresh your concepts. 

3. Using a Set

If you don't know Set is a special data structure that only stores unique value. If you try to store a duplicate value in Set then it will return false. We can also use this data structure to find the first recurring character in a given String. In Java, we have many implementations of set data structure and we'll use HashSet for this solution.

HashSet has an add() method which returns false if the element is already present in the Set. Like the previous solution, we can go through each character one by one and store them in HashSet.

If you a character is already present then add() method will return false, that is our first recurring character. At that time, we can stop processing and return that character.

Again, the time and space complexity of this solution are the same as the previous one, I mean it will take O(n) space and O(n) time to find the first recurring character in a string of N characters.

4. Java Program to find the first recurring character in a given String

Now, let's see the complete Java program to solve this Google Interview Question and find the first recurring, or duplicate, or repetitive character in the given String. It has some unit tests to verify that our solution is working fine. It also has three methods for each solution and they are checked against the same unit tests

import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Before;
import org.junit.Ignore;
import org.junit.Test;
/*
 * Problem - find the first recurring character in given String
 * Examples
 * if given String is "ABCDA" return "A"
 * if given String is "ABCDAB" return "A"
 * if given String is "ABBCDA" return "B"
 * if given String is "ABCD" return null
 */

public class GoogleTest {
    GoogleCode code;

    @Before
    public void init() {
        code = new GoogleCode();
    }

    @Test
    public void testBrutForceSolution() {
        assertEquals("A", code.bruteForce("ABCDA"));
        assertEquals("A", code.bruteForce("ABCDAB"));
        assertEquals("B", code.bruteForce("ABBCDA"));
        assertEquals(null, code.bruteForce("ABCD"));
    }

    @Test
    public void testUsingMapSolution() {
        assertEquals("A", code.usingMap("ABCDA"));
        assertEquals("A", code.usingMap("ABCDAB"));
        assertEquals("B", code.usingMap("ABBCDA"));
        assertEquals(null, code.usingMap("ABCD"));
    }

    @Test
    public void testUsingSetSolution() {
        assertEquals("A", code.usingSet("ABCDA"));
        assertEquals("A", code.usingSet("ABCDAB"));
        assertEquals("B", code.usingSet("ABBCDA"));
        assertEquals(null, code.usingSet("ABCD"));
    }
}


class GoogleCode {

    public String bruteForce(String input) {
            char[] characters = input.toCharArray();
            String firstRecurringCharacter = null;
            int firstRecurringIndex = input.length() - 1;

            for (int i = 0; i < characters.length; i++) {
                char ch = characters[i];

                for (int j = i + 1; j map = new HashMap < > ();
                    for (Character ch: chars) {
                        Integer count = map.get(ch);
                        if (count == null) {
                            map.put(ch, 1);
                        } else {
                            return "" + ch;
                        }

                    }
                    return null;
                }

                public String usingSet(String input) {
                    char[] chars = input.toCharArray();
                    Set setOfCharacters = new HashSet < > ();
                    for (Character ch: chars) {

                        // if character is already present then
                        // this method will return false and that
                        // would be our first recurring character
                        if (!setOfCharacters.add(ch)) {
                            return "" + ch; // return String for simplicity
                        }
                    }
                    return null;
                }
            }


Output - All Tests passed

The logic to test this program is written in the unit test. When you run the program, you will see all tests are passing. The program has three tests, one for each solution. Each test checks four conditions, if our solution passes for all those four conditions then logic is correct.

That's all about how to find the first recurring character in a given String. You can solve this problem in Java, C++, or Python, up to you, I have solved it in Java. As I said, this was asked in Google so it's worth practicing. It's also a good coding problem because it teaches you how clever use of data structure can reduce time complexity. If you are preparing for coding interviews and need more such questions, I suggest you join this course

More String Coding Problems from Interviews for Practice

If you are interested in solving more String based coding problems from Google, Facebook, Amazon, and other FAANG companies then here is the list of most popular string questions

• How to find all permutations of String? (solution)
• How to check if the given String is the rotation of each other? [solved]
• How to Print duplicate characters from String? (solution)
• How to convert a numeric string to an integer? (solution)
• How to check if two Strings are anagrams of each other? (solution)
• How to program to print the first non-repeated character from String? (solution)
• How to reverse String in Java using Iteration and Recursion? (solution)
• How to check if a string contains only digits?  (solution)
• How to count the number of vowels and consonants in a String? (solution)
• How to count the occurrence of a given character in String? (solution)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to reverse words in a sentence without using a library method? (solution)
• How to check if String is Palindrome? (solution)
• How to return the highest occurred character in a String? (solution)
• How to reverse a String in place in Java? (solution)
• 50+ Data Structure and Algorithms Interview Questions (questions)

Thanks for reading this article so far. If you like this Google coding Interview problem and my solution and explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S.- If you feel your data structure and algorithm skills are rusty and you need a bit of refresher then I suggest you take these coding interview preparation books and courses to quickly revise all important concepts before your interview.