Print first Non-repeating character in a string

Last Updated on March 30, 2022 by Ria Pathak

Concepts Used:

Hashing.

Difficulty Level:

Easy.

Problem Statement :

You are given a string str consisting of lowercase Latin letters. Find the first non-repeating character in str.

Note: You have to traverse the string only once.

See original problem statement here

Tets Case:

Input:
prepbytes

Output:
1

Explanation:
In the string 'prepbytes', we start traversing from the first index(since first non repeating character is to be answered).
'p' does not satisfy the criteria because it is repeated at index 3. 'r' is the first char which is non repeating.

Solving Approach:

1. This problem can be easily solved with hash maps(hashing).
2. Start from 0th index and store the frequency of each letter.
3. Run another loop wich checks the first element with 1 as the frequency.

Solutions:

#include<stdlib.h>
int main()
{int t;scanf("%d",&t);
while(t--)
{
  int n;scanf("%d",&n);
  char s[n];
  for(int i=0;i<n;i++)scanf("%c",&s[i]);
  int count[27];
  for(int i=0;i<27;i++)
  count[i]=0;
  for(int i=0;i<n;i++)
  count[s[i]-'a']++;int flag=-1;
  for(int i=0;i<n;i++)
  {
    if(count[s[i]-'a']==1)
    {
      flag=i;
      break;
    }
  }
  if(flag==-1)
  printf("-1\n");
  else
  printf("%c\n",s[flag]);
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;cin>>t;
 while(t--)
{
int n;cin>>n;
string s;
cin>>s;
int a[26]={0};
for(int i=0;i<n;i++)
{
  a[s[i]-'a']++;
}
int flag=0;
for(int i=0;i<n;i++)
{
  if(a[s[i]-'a']==1)
  {
    flag=1;
    cout<<s[i]<<"\n";
    break;
  }
}
if(flag==0)
cout<<-1<<"\n";
}
return 0;
}

import java.util.*;
class Solution{
public static void main(String args[]){
    Scanner sc=new Scanner(System.in);

    int t=sc.nextInt();
    while(t-->0){

        int n=sc.nextInt();
        String s=sc.next();

        int a[]=new int[26];

        for(int i=0;i<n;i++)
        a[s.charAt(i)-'a']++;

        int flag=0;

        for(int i=0;i<n;i++){
            if(a[s.charAt(i)-'a']==1)
            {
                flag=1;
                System.out.println(s.charAt(i));
                break;
            }
        }
        if(flag==0)
        System.out.println(-1);
    }
}
}

This article tried to discuss the concept of hashing. Hope this blog helps you understand and solve the problem. To practice more problems on hashing you can check out MYCODE | Competitive Programming.