Teaching Kids Programming – Find First Recurring Character using Hash Table/Set

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a lowercase alphabet string s, return the index of the first recurring character in it. If there are no recurring characters, return -1.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “abcda”
Output
4
Explanation
The a at index 4 is the first recurring character.

Example 2
Input
s = “abcde”
Output
-1
Explanation
No recurring characters in this string.

Example 3
Input
s = “aaaaa”
Output
1
Explanation
We want the first recurring character.
There are only 26 character try using array and storing the passed value

Find First Recurring Character using Hash Table

We use {} to declare a dictionary aka hashmap which contains the key-value pairs. The time complexity to insert, update, lookup and remove for a hash map is O(1) constant.

1
2
3
4
5
6
7
8

class Solution:
    def solve(self, s):
        seen = {}
        for i,j in enumerate(s):
            if j in seen:                
                return i
            seen[j] = i
        return -1

class Solution:
    def solve(self, s):
        seen = {}
        for i,j in enumerate(s):
            if j in seen:                
                return i
            seen[j] = i
        return -1

We use enumerate to return the tuple of index and value. Then we check if the entry has appeared in dictionary. If yes, return current index, otherwise insert to the dictionary.

Find First Recurring Character using Hash Set

The set() declares a hash set which stores unique elements. And the time complexity to insert, remove and lookup is O(1) constant. We can safely replace the dictionary with set since we only care about the occurences.

1
2
3
4
5
6
7
8

class Solution:
    def solve(self, s):
        seen = set()
        for i,j in enumerate(s):
            if j in seen:                
                return i
            seen.add(j)
        return -1

class Solution:
    def solve(self, s):
        seen = set()
        for i,j in enumerate(s):
            if j in seen:                
                return i
            seen.add(j)
        return -1

–EOF (The Ultimate Computing & Technology Blog) —