Problem Statement : Given a word, find the first recurring letter.
Example 1.) Input : ABCD. Output : Null Explanation : None of the letters repeat or recur. Example 2.) Input : DERDER Output : D Explanation : D is the first recurring letter. Example 3.) Input : QWEEWQ Output : Q Explanation : Q is the first recurring letter.
Now there are 2 approaches.
- Apply 2 loops. (i and j)
- First loop i.e. ‘i’ will iterate through from first letter till last letter of the word.
- Second loop i.e. ‘j’ will iterate from ‘i’ to last letter.
- On each iteration of ‘j’ check if the ‘ith‘ letter is repeating. If yes you got your O/P.
- This approach has O(n2) Time complexity as we are iterating through the letters of the word twice, using 2 loops.
Below is the code.
- This approach is required when you are giving interviews in Tier 1 companies because they are more worried over ‘Time complexity’.
- The approach uses single loop thus having time complexity O(n), uses less memory.
- The approach also uses easy string manipulation.
- So let’s look into the code below and check time complexity.