6.LeftMost_NonRepeating.md

Left Most Non-repeating

• Left Most Non-repeating
  • Problem Statement
  • Algorithm
  • Python Code

Problem Statement

Write a function nonRep() that takes a string as input and returns the index of the leftmost non-repeating character in the string. If there are no non-repeating characters, the function should return -1.

Example: Input: "geeksforgeeks"
Output: 5
Explanation: The leftmost non-repeating character is 'f' and its index is 5.

Algorithm

1. Initialize an integer array fI of size 256, to store the first occurrence of each character of the string. Initialize all elements of the array to -1.
2. Traverse the string from left to right and for each character calculate the following:
   • If its first occurrence has not been found yet, store its index in the array fI.
   • If its first occurrence has already been found, update the corresponding element of the array as -2.
3. Traverse the fI array and find the index of the first element which is not -1 or -2, and return its value.

Python Code

'''
Time: O(N+CHAR)
Space: O(CHARA)
'''
def nonRep(str):
    CHAR = 256
    fI = [-1] * CHAR

    for i in range(len(str)):
        if fI[ord(str[i])] == -1:
            fI[ord(str[i])] = i
        else:
            fI[ord(str[i])] = -2

    res = float("inf")
    for i in range(CHAR):
        if fI[i] >= 0:
            res = min(res, fI[i])

    return res if res != float("inf") else -1

str = "geeksforgeeks"
print("Index of leftmost non-repeating element:")
print(nonRep(str))