FOR FREE MATERIALS

You are given a string. You need to return the 1st recurring character in the string.

Here, according to the question we need to find the first recurring character in the string.

For example: “A B C A”

First recurring character = ‘A’

Example:

“B C A B A” = ‘B’

Recurring characters → ‘B’ ‘A’

But first recurring character → ‘B’

For string “ ‘ → having 0 length 

Return None

Or

“ “ → have length > 0 but contain only spaces also returns None

Bruteforce Approach

‘A B B A’

Let the string length be N

So, here We will check for each character whether it is present from the (character’s current position + 1) to the second last and stop if found return the characters else if such character not found return None.

Line:

Example: ‘A B BA’

Check ‘A’ in ‘B BA’ found → return ‘A’

Example: ‘ABC’

Check ‘A’ in ‘BC’ → not found

Check ‘B’ in ‘C’ → not found

∴ Return ‘None’

Using these approach in the worst case it will take O(n2)

‘A B C’                 / n =3

For ‘A’ → 2 → n – 1

For ‘B’ → 1 → (n – 1) – 1 = n – 2

∴ (n – 1) + (n – 2) + ……………. 1 =  = O(n2)

Better Approach

Use the concept of dictionary which features the time of insertion / deletion / updation to O(1) on range

 Step 1: Check whether the language of string

              if length(string) == 0             

              return None

             Or check whether string is filled with blank space

              if string contains space return None

Step 2: Create a blank dictionary

Step 3: Run a loop on length of the string

Step 4: Check whether current character present in the dictionary.

             if present → return the character

             else

                  Store it in the dictionary where key is the current character and its value = 1

Step 5: Repeat Step 3 – 4 until reach end of the loop

Step 6: Repeat None if such a character not – found.