Given a string, find its first non-repeating character

Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’ and if input string is “GeeksQuiz”, then output should be ‘G’.

find-first-non-repeated-character-in-a-string
We can use string characters as index and build a count array. Following is the algorithm.

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of each
 character, if you find an element who's count is 1, return it.

Example:

Input string: str = geeksforgeeks
1: Construct character count array from the input string.
   ....
  count['e'] = 4
  count['f'] = 1
  count['g'] = 2
  count['k'] = 2
  ……
2: Get the first character who's count is 1 ('f').

Implementation:

C/C++

// C program to find first non-repeating character 
#include<stdlib.h> 
#include<stdio.h> 
#define NO_OF_CHARS 256 
  
/* Returns an array of size 256 containg count 
   of characters in the passed char array */
int *getCharCountArray(char *str) 
{ 
   int *count = (int *)calloc(sizeof(int), NO_OF_CHARS); 
   int i; 
   for (i = 0; *(str+i);  i++) 
      count[*(str+i)]++; 
   return count; 
} 
  
/* The function returns index of first non-repeating 
   character in a string. If all characters are repeating  
   then returns -1 */
int firstNonRepeating(char *str) 
{ 
  int *count = getCharCountArray(str); 
  int index = -1, i; 
  
  for (i = 0; *(str+i);  i++) 
  { 
    if (count[*(str+i)] == 1) 
    { 
      index = i; 
      break; 
    }    
  }   
    
  free(count); // To avoid memory leak 
  return index; 
} 
  
/* Driver program to test above function */
int main() 
{ 
  char str[] = "geeksforgeeks"; 
  int index =  firstNonRepeating(str); 
  if (index == -1)   
    printf("Either all characters are repeating or string is empty"); 
  else
   printf("First non-repeating character is %c", str[index]); 
  getchar(); 
  return 0; 
} 

Java

// Java program to find first non-repeating character 
  
class GFG  
{ 
    static final int NO_OF_CHARS = 256; 
    static char count[] = new char[NO_OF_CHARS]; 
      
    /* calculate count of characters  
       in the passed string */
     static void getCharCountArray(String str)  
     { 
         for (int i = 0; i < str.length();  i++) 
              count[str.charAt(i)]++; 
     } 
       
    /* The method returns index of first non-repeating 
       character in a string. If all characters are repeating  
       then returns -1 */
    static int firstNonRepeating(String str) 
    { 
        getCharCountArray(str); 
        int index = -1, i; 
       
        for (i = 0; i < str.length();  i++) 
        { 
            if (count[str.charAt(i)] == 1) 
            { 
                index = i; 
                break; 
            }    
        }   
        
      return index; 
    } 
  
    // Driver method 
    public static void main (String[] args) 
    { 
        String str = "geeksforgeeks"; 
        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)); 
    } 
} 

Python

# Python program to print the first non-repeating character 
NO_OF_CHARS = 256
  
# Returns an array of size 256 containg count 
# of characters in the passed char array 
def getCharCountArray(string): 
    count = [0] * NO_OF_CHARS 
    for i in string: 
        count[ord(i)]+=1
    return count 
  
# The function returns index of first non-repeating 
# character in a string. If all characters are repeating 
# then returns -1 
def firstNonRepeating(string): 
    count = getCharCountArray(string) 
    index = -1
    k = 0
  
    for i in string: 
        if count[ord(i)] == 1: 
            index = k 
            break
        k += 1
  
    return index 
  
# Driver program to test above function 
string = "geeksforgeeks"
index = firstNonRepeating(string) 
if index==1: 
    print "Either all characters are repeating or string is empty"
else: 
    print "First non-repeating character is " + string[index] 
  
# This code is contributed by Bhavya Jain 

C#

// C# program to find first non-repeating character 
using System; 
using System.Globalization; 
  
class GFG { 
      
    static int NO_OF_CHARS = 256; 
    static char []count = new char[NO_OF_CHARS]; 
      
    /* calculate count of characters  
    in the passed string */
    static void getCharCountArray(string str)  
    { 
        for (int i = 0; i < str.Length; i++) 
            count[str[i]]++; 
    } 
      
    /* The method returns index of first non-repeating 
    character in a string. If all characters are  
    repeating then returns -1 */
    static int firstNonRepeating(string str) 
    { 
        getCharCountArray(str); 
        int index = -1, i; 
      
        for (i = 0; i < str.Length; i++) 
        { 
            if (count[str[i]] == 1) 
            { 
                index = i; 
                break; 
            }  
        }  
          
    return index; 
    } 
      
    // Driver code 
    public static void Main() 
    { 
        string str = "geeksforgeeks"; 
        int index = firstNonRepeating(str); 
          
        Console.WriteLine(index == -1 ? "Either " + 
        "all characters are repeating or string " + 
        "is empty" : "First non-repeating character"
        + " is " + str[index]); 
    } 
} 
  
// This code is contributed by Sam007 

PHP

<?php 
// PHP program to find  
// first non-repeating  
// character 
$NO_OF_CHARS = 256; 
$count=array_fill(0, 200, 0); 
  
/* calculate count  
   of characters in   
   the passed string */
function getCharCountArray($str)  
{ 
    global $count; 
    for ($i = 0;  
         $i < strlen($str); $i++) 
        $count[ord($str[$i])]++; 
} 
  
/* The method returns index  
of first non-repeating 
character in a string. If  
all characters are repeating  
then returns -1 */
function firstNonRepeating($str) 
{ 
    global $count; 
    getCharCountArray($str); 
    $index = -1; 
    for ($i = 0;  
         $i < strlen($str); $i++) 
    { 
        if ($count[ord($str[$i])] == 1) 
        { 
            $index = $i; 
            break; 
        }  
    }  
      
return $index; 
} 
  
// Driver code 
$str = "geeksforgeeks"; 
$index = firstNonRepeating($str); 
if($index == -1) 
echo "Either all characters are" .  
     " repeating or string is empty"; 
else
echo "First non-repeating ".  
            "character is ". 
               $str[$index]; 
  
// This code is contributed by mits 
?> 

Output:

First non-repeating character is f

Can we do it by traversing the string only once?
The above approach takes O(n) time, but in practice it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not good in practice. In real situations, your string is expected to be much larger than your alphabet. Take DNA sequences for example: they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).
We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string. Thanks to Ben for suggesting this approach.

Following is implementation of the extended approach that traverses the input string only once.

C++

// CPP program to find first non-repeating 
// character 
#include <bits/stdc++.h> 
using namespace std; 
#define NO_OF_CHARS 256 
  
/* The function returns index of the first 
   non-repeating character in a string. If 
   all characters are repeating then 
   reurns INT_MAX */
int firstNonRepeating(char *str) 
{ 
    pair<int, int> arr[NO_OF_CHARS]; 
  
    for (int i = 0; str[i]; i++) 
    { 
        (arr[str[i]].first)++; 
        arr[str[i]].second = i; 
    } 
  
    int res = INT_MAX; 
    for (int i = 0; i < NO_OF_CHARS; i++) 
  
        // If this character occurs only 
        // once and appears before the 
        // current result, then update the 
        // result 
        if (arr[i].first == 1) 
            res = min(res, arr[i].second); 
  
    return res; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    char str[] = "geeksforgeeks"; 
    int index = firstNonRepeating(str); 
    if (index == INT_MAX) 
        printf("Either all characters are "
              "repeating or string is empty"); 
    else
        printf("First non-repeating character"
               " is %c", str[index]); 
    return 0; 
} 

C

#include <stdlib.h> 
#include <stdio.h> 
#include <limits.h> 
#define NO_OF_CHARS 256 
  
// Structure to store count of a character and index of the first 
// occurrence in the input string 
struct countIndex { 
   int count; 
   int index; 
}; 
  
/* Returns an array of above structure type. The size of 
   array is NO_OF_CHARS */
struct countIndex *getCharCountArray(char *str) 
{ 
   struct countIndex *count = 
        (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS); 
   int i; 
   for (i = 0; *(str+i);  i++) 
   { 
      (count[*(str+i)].count)++; 
  
      // If it's first occurrence, then store the index 
      if (count[*(str+i)].count == 1) 
         count[*(str+i)].index = i; 
   } 
   return count; 
} 
  
/* The function returns index of the first non-repeating 
    character in a string. If all characters are repeating 
    then reurns INT_MAX */
int firstNonRepeating(char *str) 
{ 
  struct countIndex *count = getCharCountArray(str); 
  int result = INT_MAX, i; 
  
  for (i = 0; i < NO_OF_CHARS;  i++) 
  { 
    // If this character occurs only once and appears 
    // before the current result, then update the result 
    if (count[i].count == 1 && result > count[i].index) 
       result = count[i].index; 
  } 
  
  free(count); // To avoid memory leak 
  return result; 
} 
  
/* Driver program to test above function */
int main() 
{ 
  char str[] = "geeksforgeeks"; 
  int index =  firstNonRepeating(str); 
  if (index == INT_MAX) 
    printf("Either all characters are repeating or string is empty"); 
  else
   printf("First non-repeating character is %c", str[index]); 
  getchar(); 
  return 0; 
} 

Java

// Java program to find first non-repeating character 
// Note : hashmap is used 
  
import java.util.HashMap; 
  
class CountIndex 
{ 
    int count,index; 
      
    // constructor for first occurrence 
    public CountIndex(int index) { 
        this.count = 1; 
        this.index = index; 
    } 
      
    // method for updating count 
    public void incCount() { 
        this.count++; 
    } 
} 
class GFG  
{ 
    static final int NO_OF_CHARS = 256; 
      
    static HashMap<Character, CountIndex> hm = new HashMap<Character, CountIndex>(NO_OF_CHARS); 
      
    /* calculate count of characters  
       in the passed string */
     static void getCharCountArray(String str)  
     { 
         for (int i = 0; i < str.length();  i++) 
         { 
            // If character already occurred,  
             if(hm.containsKey(str.charAt(i))) 
             { 
                 // updating count 
                 hm.get(str.charAt(i)).incCount(); 
             } 
               
            // If it's first occurrence, then store the index and count = 1 
             else
             { 
                 hm.put(str.charAt(i), new CountIndex(i)); 
             } 
                   
         }     
     } 
       
    /* The method returns index of first non-repeating 
       character in a string. If all characters are repeating  
       then returns -1 */
    static int firstNonRepeating(String str) 
    { 
        getCharCountArray(str); 
        int result = Integer.MAX_VALUE, i; 
       
        for (i = 0; i < str.length();  i++) 
        { 
             // If this character occurs only once and appears 
            // before the current result, then update the result 
            if (hm.get(str.charAt(i)).count == 1 && result > hm.get(str.charAt(i)).index){ 
                 result = hm.get(str.charAt(i)).index; 
            } 
                
        }   
        
      return result; 
    } 
  
    // Driver method 
    public static void main (String[] args) 
    { 
        String str = "geeksforgeeks"; 
        int index =  firstNonRepeating(str); 
          
        System.out.println(index == Integer.MAX_VALUE ? "Either all characters are repeating " + 
              " or string is empty" : "First non-repeating character is " +  str.charAt(index)); 
    } 
} 

C#

// C# program to find first  
// non-repeating character  
// Note : hashmap is used  
using System; 
using System.Collections.Generic; 
  
class CountIndex 
{ 
    public int count, index; 
  
    // constructor for first occurrence  
    public CountIndex(int index) 
    { 
        this.count = 1; 
        this.index = index; 
    } 
  
    // method for updating count  
    public virtual void incCount() 
    { 
        this.count++; 
    } 
} 
  
class GFG 
{ 
    public const int NO_OF_CHARS = 256; 
  
    public static Dictionary<char,  
                  CountIndex> hm = new Dictionary<char, 
                                       CountIndex>(NO_OF_CHARS); 
  
    /* calculate count of characters  
    in the passed string */
    public static void getCharCountArray(string str) 
    { 
        for (int i = 0; i < str.Length; i++) 
        { 
            // If character already occurred,  
            if (hm.ContainsKey(str[i])) 
            { 
                // updating count  
                hm[str[i]].incCount(); 
            } 
  
            // If it's first occurrence, then  
            // store the index and count = 1  
            else
            { 
                hm[str[i]] = new CountIndex(i); 
            } 
  
        } 
    } 
  
    /* The method returns index of first  
    non-repeating character in a string.  
    If all characters are repeating then 
    returns -1 */
    internal static int firstNonRepeating(string str) 
    { 
        getCharCountArray(str); 
        int result = int.MaxValue, i; 
  
        for (i = 0; i < str.Length; i++) 
        { 
            // If this character occurs only  
            // once and appears before the  
            // current result, then update the result  
            if (hm[str[i]].count == 1 &&  
                result > hm[str[i]].index) 
            { 
                result = hm[str[i]].index; 
            } 
  
        } 
  
    return result; 
    } 
  
    // Driver Code 
    public static void Main(string[] args) 
    { 
        string str = "geeksforgeeks"; 
        int index = firstNonRepeating(str); 
  
        Console.WriteLine(index == int.MaxValue ?  
                          "Either all characters are repeating " +  
                          " or string is empty" :  
                          "First non-repeating character is " +  
                                                   str[index]); 
    } 
} 
  
// This code is contributed by Shrikant13 

Output:

First non-repeating character is f

Related Problem : K’th Non-repeating Character

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Given a string, find its first non-repeating character

C/C++

Java

Python

C#

PHP

C++

C

Java

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books