You are given a string. You need to return the 1st recurring character in the string.
INPUT | OUTPUT |
“A B C A” | ‘A’ |
“B C A B A” | ‘B’ |
“A B C” | None |
“A B B A” | ‘A’ |
“ “ | None |
“ ‘ | None |
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.
Time complexity: / let length of string = n
Worst case:
For loop → O(length of string)
O(n)
For loop → dictionary → search on an average - O(1)
Time complexity: O(n)
Space complexity: O(n) / worst case: i.e. no repetition of characters