Easy methods to discover first recurring or duplicate character in given String? [Solved]

Good day guys, whereas browsing the Web for a few weeks again, I come to
know that this drawback was requested on Google interviews,
discover the primary recurring character in a given String. I do not know if
that is true however this appears like a quite simple coding drawback from Google’s
Interview commonplace. If it was certainly requested, then that man should have been
very fortunate. Anyway, I appreciated this coding drawback and thought to put in writing about
it, as a result of it is a good coding drawback to examine candidates’
knowledge construction and algorithms abilities
as a result of it is difficult. It is difficult as a result of it is very simple to make a mistake
assuming only one recurring character in String, which you need to
keep away from. Even when it was not requested on Google, you’ll probably discover this drawback
on numerous startups, and different IT firms like Infosys, TCS, Cognizant,
Microsoft, and perhaps
Amazon. 

The brute pressure or most intuitive technique to remedy this drawback is to take one
character at a time, ranging from the first character, after which examine
with all of the characters, if it matches, then it is the primary recurring
character. Simply return the character and you’re accomplished.

For instance, if the enter string is “ABCDAB”
then there are two duplicate characters in it however “A” is the primary recurring
character. In the event you begin with the letter “A” and examine it with “B”, “C”,
“D”, “A”, you will see that it matches with the final “A”, therefore that is the
first
recurring character.

Now, you should examine and see if this subsequent index is decrease than the
earlier index, if sure, then
swap and will probably be the brand new first recurring character as a result of it is noticed
first within the String. When you full with all characters, you should have
your reply in variable “firstRecurringCharacter”.

Now, we’re utilizing an information construction referred to as Map, or hash desk, or dictionary
in Python to enhance our resolution. On this resolution, we undergo all
characters one after the other and retailer them within the
hash desk
as key and worth as 1 to point that we have now seen this character
earlier than. 

By default, the important thing and worth will probably be null for an unseen character. Whenever you
hit a recurring character, you will see that that it is already current on the
map. At that time, you may cease processing and return that character. Achieved.

The time complexity of this resolution is
O(n) as a result of we’re simply visiting
every character one time. If there’s n character in String then we’ll name
the
put() technique
N occasions. Because the time complexity of storing a key-value pair within the hash
desk is O(1), the time
complexity of our resolution can be
O(n)*
O(1) = O(n).

It is a good instance of how utilizing an information construction can enhance efficiency
and simplify an algorithm. It’s also a very good instance of the area vs time
tradeoff as a result of we spend
O(n) area to scale back time
complexity from O(N^2) to O(n).
By the best way, in case you are new to time and area complexity, you may try
these
knowledge constructions and algorithms courses to be taught and refresh your ideas. 

If you do not know Set is a particular knowledge construction that solely shops distinctive
worth. In the event you attempt to retailer a reproduction worth in Set then it should return
false. We are able to additionally use this knowledge construction to search out the primary recurring
character in a given String. In Java, we have now many implementations of set
knowledge construction and we’ll use HashSet for this resolution.

HashSet has an add() technique which
returns false if the factor is already current within the Set. Just like the
earlier resolution, we are able to undergo every character one after the other and retailer
them in
HashSet.

Now, let’s examine the whole Java program to unravel this Google Interview
Query and discover the primary recurring, or duplicate, or repetitive character
within the given String. It has some unit checks to confirm that our resolution is
working effective. It additionally has three strategies for every resolution and they’re
checked in opposition to the identical unit checks

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.Earlier than;
import org.junit.Ignore;
import org.junit.Check;


public class GoogleTest {
    GoogleCode code;

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

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

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

    @Check
    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 enter) {
            char[] characters = enter.toCharArray();
            String firstRecurringCharacter = null;
            int firstRecurringIndex = enter.size() - 1;

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

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

                    }
                    return null;
                }

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

                        
                        
                        
                        if (!setOfCharacters.add(ch)) {
                            return "" + ch; 
                        }
                    }
                    return null;
                }
            }



Output - All Assessments handed

If you’re thinking about fixing extra String based mostly coding issues from
Google, Fb, Amazon, and different FAANG firms then right here is the listing of
hottest string questions

• Easy methods to discover all permutations of String? (resolution)
• Easy methods to examine if the given String is the rotation of one another? [solved]
• Easy methods to Print duplicate characters from String? (resolution)
• Easy methods to convert a numeric string to an integer? (resolution)
• Easy methods to examine if two Strings are anagrams of one another? (resolution)
• Easy methods to program to print the primary non-repeated character from String?
  (resolution)
• Easy methods to reverse String in Java utilizing Iteration and Recursion? (resolution)
• Easy methods to examine if a string incorporates solely digits?  (resolution)
• Easy methods to rely the variety of vowels and consonants in a String? (resolution)
• Easy methods to rely the incidence of a given character in String? (resolution)
• 10 Algorithms Programs to Crack Programming Job Interviews (programs)
• Easy methods to reverse phrases in a sentence with out utilizing a library technique? (resolution)
• Easy methods to examine if String is Palindrome? (resolution)
• Easy methods to return the very best occurred character in a String? (resolution)
• Easy methods to reverse a String in place in Java? (resolution)
• 50+ Information Construction and Algorithms Interview Questions (questions)

P. S.- In the event you really feel your knowledge construction and algorithm abilities are rusty
and also you want a little bit of refresher then I recommend you are taking these
coding interview preparation books and programs
to shortly revise all vital ideas earlier than your interview.