Find the first repeated character in a string in Python
In this tutorial, we are going to learn how to find the first repeated character in Python.
Problem Statement
Given a string, we need to find the first repeated character in the string, we need to find the character which occurs more than once and whose index of the first occurrence is least with Python programming.
If there is no repeating character, print -1.
I hope, you understood what we are exactly going to do. So let’s continue…
Brute force method
Traverse through the entire string from starting to end.
For every character check whether it is repeating or not.
If there is no repeated character print -1.
Time Complexity-O(N^2)
str="codespeedy" a=0 for i in range(0 , len(str) ): #traversing through the entire string if a==1: break for j in range(i+1 , len(str)): #traversing characters after the current one if str[i]==str[j]: print(str[i]) a=1 #this character is the first repeating character break if a==0: print(-1)
OUTPUT-
d
Using Hashing -Two traversals of the string
Use a dictionary to count how many times each character occurs in the string –the keys are characters and the values are frequencies.
- Traverse through the entire string.
- Check whether the current character is already present in the dictionary.
- If it is present, then update the frequency of the current character by 1 i.e dict[str[i]]++.
- Else insert the characters with frequency 1 i.e. dict[str[i]]=1
In the second traversal, for every character check whether it is repeating or not by checking dict[str[i]].
If we find the first repeated character, we break from the loop.
Time Complexity-O(N)
Below is the Python code implementing this method for our task:
str="codespeedy" dict={} n=len(str) for i in range(0 , n): if str[i] in dict: dict[str[i]]+=1; else: dict[str[i]]=1 a=0 for i in range(0 , n): if dict[str[i]]>1: print(str[i]) a=1 break if a==0: print(-1)
OUTPUT
d
Using Hashing -One traversal of the string
Start by initializing the ans to len(str)+1, which will be used to store the index of the first repeating character.
We use a dictionary but here we store the character and its first occurrence.
We will update the minimum index whenever we find an element that has been visited.
In the end, if the ans is len(str)+1, means there is no repeated character, we return -1.
Else return str[ans] which is the first repeating character.
str="codespeedy" dict={} n=len(str) ans=n+1 for i in range(0 , n): if str[i] in dict: ans=min(ans , dict[str[i]]) else: dict[str[i]]=i if ans==n+1: print(-1) else: print(str[ans])
OUTPUT
d
You may also read
Leave a Reply