Find the first repeated character in a string in Python

By Meetali Tomer

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