Leftmost Non-repeating Element

Problem Statement: Given a string, find the leftmost non-repeating character of the string. i.e The first character that does not appear again in the further string.

Examples:

Example 1:
Input: takeUforward
Output: t
Explanation: Character ‘t’ is the left-most non-repeating character or the first non-repeating character.

Example 2:
Input: Engineer
Output: g
Explanation: Character ‘g’ is the left-most non-repeating character or the first non-repeating character.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive approach

Approach

  • Select the first character of the string and compare it with every other character in            the string.
  • If the current character does not match with any of the further characters in the string then immediately return / Print that character.
  • Else, repeat the steps 1st and 2nd until the whole string is traversed or until we got out an answer.
  • if all the characters are traversed or the string is empty then return or print -1.
  • Return the answer.

Code:

C++ Code

#include <iostream>

using namespace std;

int firstNonRepeating(string str) {
  for (int i = 0; i < str.size(); i++) {
    int flag = 0;
    for (int j = 0; j < str.size(); j++) {
      if (i != j && str[i] == str[j]) {
        flag = 1;
        break;
      }
    }
    if (flag == 0) {
      return i;
    }
  }
  return -1;
}

int main() {
  string str = "takeuforward";
  int index = firstNonRepeating(str);
  if (index == -1)
    cout << "Either all characters are repeating or "
  "string is empty";
  else
    cout << "First non-repeating character is " <<
    str[index];
  getchar();
  return 0;
}

Output: First non-repeating character is t

Time Complexity: O(N^2)

Space Complexity: O(1)

Java Code

class TUF {

  static int firstNonRepeating(String str) {
    for (int i = 0; i < str.length(); i++) {
      int flag = 0;
      for (int j = 0; j < str.length(); j++) {
        if (i != j && str.charAt(i) == str.charAt(j)) {
          flag = 1;
          break;
        }
      }
      if (flag == 0) {
        return i;
      }
    }

    return -1;
  }

  public static void main(String[] args) {
    String str = "takeuforward";
    int index = firstNonRepeating(str);

    System.out.println(
      index == -1 ?
      "Either all characters are repeating or string " +
      "is empty" :
      "First non-repeating character is " +
      str.charAt(index));
  }
}

Output: First non-repeating character is t

Time Complexity: O(N^2)

Space Complexity: O(1)

Solution 2: Using Frequency Array

Approach

  • Make a count array of size 256 i.e all the alphabets and symbols.
  • We will initialize all the elements in this array to -1.
  • Then loop through the string character by character and check if the frequency array element with this character has it’s index as -1 or not. 
  • If it is -1 then change it to ‘i’ i.e (our looping variable) and if it is not -1 then this means that this character has already appeared before, so change it to -2. 
  • In the end all the repeating characters will be changed to -2 and all non-repeating characters will contain the index where they occur. Now we can just loop through all the non-repeating characters and find the minimum index or the first index.

Code:

C++ Code

# include<bits/stdc++.h>
 
using namespace std;

int firstNonRepeating(string str) {
    int fi[256]; // frequency array
 
    for(int i = 0; i<256; i++)
    {
        fi[i] = -1; // initalizing every index of frequency array with -1.
    }
 
    // sets all repeating characters to -2 and non-repeating characters
   // contain the index where they occur
    for(int i = 0; i<str.length(); i++) 
    {
        if(fi[str[i]] == -1) 
        {
            fi[str[i]] = i;
        }
        else 
        {
            fi[str[i]] = -2;
        }
    }
 
    // If this character is not -1 or -2 then it
    // means that this character occurred only once
    // so find the min index of all characters that
    // occur only once, that's our first index
    int res = INT_MAX;
 
    for(int i = 0; i<256; i++) 
    {
        if(fi[i] >= 0)
        {
            res = min(res, fi[i]); // finding the minimum index of 
            //non-repeating character.
        }
    }
     
    // if res remains INT_MAX, it means there are no
    // characters that repeat only once or the string is empty
    if(res == INT_MAX)
    {
        return -1;
    }
    return res;
}
 
int main(){
    string str;
      str = "takeuforward";
    int firstIndex = firstNonRepeating(str);
    if (firstIndex == -1)
        cout<<"Either all characters are repeating or string is empty";
    else
        cout<<"First non-repeating character is "<< str[firstIndex];
     
    return 0;
}

Output: First non-repeating character is t

Time Complexity: O(N)

Space Complexity: O(1) 

Reason: 256 is a constant so Space complexity is O(1).

Java Code

public class TUF {

  public static int firstNonRepeating(String str) {

    int[] fi = new int[256]; // frequency array

    // initializing all elements to -1
    for (int i = 0; i < 256; i++) {
      fi[i] = -1;
    }

    // sets all repeating characters to -2 and non-repeating characters
    // contain the index where they occur
    for (int i = 0; i < str.length(); i++) {
      if (fi[str.charAt(i)] == -1) {
        fi[str.charAt(i)] = i;
      } else {
        fi[str.charAt(i)] = -2;
      }
    }

    // If this character is not -1 or -2 then it
    // means that this character occurred only once
    // so find the min index of all characters that
    // occur only once, that's our first index
    int res = Integer.MAX_VALUE;

    for (int i = 0; i < 256; i++) {
      if (fi[i] >= 0) {
        res = Math.min(res, fi[i]);
      }
    }

    // if res remains  Integer.MAX_VALUE, it means there are no
    // characters that repeat only once or the string is empty
    if (res == Integer.MAX_VALUE) {
      return -1;
    }
    return res;
  }

  public static void main(String args[]) {
    String str;
    str = "takeuforward";
    int firstIndex = firstNonRepeating(str);
    if (firstIndex == -1) {
     System.out.println("Either all characters are repeating or string is empty");
    } else {
     System.out.println("First non-repeating character is "+str.charAt(firstIndex));
    }
  }
}

Output: First non-repeating character is t

Time Complexity: O(N)

Space Complexity: O(1) 

Reason: 256 is a constant so Space complexity is O(1).

Special thanks to Abhishek Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article