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.
Approach 1
- 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.
Approach 2
- 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.
I was curious if you ever thought of changing the layout of
your site? Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having 1 or
two images. Maybe you could space it out better?
Yes, Right , i need improvement on my content design part.
It’s a pity you don’t have a donate button! I’d most certainly donate to this excellent blog!
I guess for now i’ll settle for book-marking and adding your RSS feed to my
Google account. I look forward to fresh updates and will talk
about this site with my Facebook group. Talk soon!
Heya i’m for the primary time here. I came across this board and I find It really helpful & it helped me out a lot.
I hope to give one thing again and aid others such
as you helped me.
Hi I am so thrilled I found your weblog, I really found you by accident, while I was browsing
on Google for something else, Anyways I am here now and would
just like to say cheers for a tremendous post and a all round interesting
blog (I also love the theme/design), I don’t have time to read it all at the moment but I have bookmarked it
and also included your RSS feeds, so when I have time
I will be back to read a great deal more, Please do
keep up the awesome job.