First character

Last Updated on March 23, 2022 by Ria Pathak

Concepts Used

String, Hashing

Difficulty Level

Easy

Problem Statement (Simplified):

Find the first non-repeating character in the string, print -1 if all characters are repeating.

See original problem statement here

Test Case

Input:
2
prepbytesreport
mettme

Output:
4
-1

Explanation:
Case-1:
'p' repeats at index 3 and 11.
'r' repeats at index 9 and 13.
'e' repeats at index 7 and 10.
'p' has already been scanned, which means it has occurred before.
'b' does not appear after the current position, hence this is the first non-repeating character of the string. So the current index i.e. 4 is our answer.

Case-2:
'm' repeats at index 4.
'e' repeats at index 5.
't' repeats at index 3.
't' has already been scanned, which means it has occurred before.
'm' has already been scanned, which means it has occurred before.
'e' has already been scanned, which means it has occurred before.
As we scanned our complete string but no non-repeating character was found so we print -1 as our answer.

Solving Approach :

Bruteforce Approach:

1) As we have to find the first non-repeating character, so we will scan the whole complete string.
2) For every character, we will scan the whole complete string, and see if the current character appears at any index except the current index. If yes, the given character is repeating. If no such value is found, that means this is the first non-repeating character and we print the current index.
3) If no such character is found in complete string, that means string contains all repeating character, so we print -1.
4) The Above approach scans whole string for every character, which means it take O(N²) time complexity which is inefficient for larger strings. We can decrease time complexity by using a single loop in the following approach.

Efficient Approach:

1) In this approach, We can find the first non-repeating character if we know the frequency of all characters.

2) To maintain the frequency of characters, we use hashing technique that uses a hash table.

• Hash Table: A hash table is an array, where each index represents a Key and value at index represents value associated with the key.

3) Here character can be converted easily into a valid index, by substracting ASCII value of A from it, hence each index starting from 0 to 25 represents characters A to Z respectively.

4) After counting the frequency of all characters in the hash table, we print the index of the first character in string who appears exactly once in the string and have hash value 1.

5) If no such character is found we print -1.

Example

• Let’s assume, given string is prepbyters, we use a hash table to count the total number of appearances of each character in the given string.

• We increment the value of hash table by 1 for the current scanned character, where each index represents a unique character.

• After scanning whole string our hash table becomes,

• In the above hash table, every index represents the count of character in the given string, where every index represents a unique character.

• We again scan string from start, if the current character has a value greater than 1, which means it repeats in the given string. If the value is 1, it only presents at the current index and is non-repeating. As soon as we get such an index, we print the current index as it is the first non-repeating character in the string.

• If the whole string is scanned, but no such index is found we print -1.

Solutions

#include <stdio.h>

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    char s[9999];
    scanf("%s",s);

    int hash[26] = {0}, flag=1;

    for(int i=0; i<strlen(s); i++)
      hash[s[i]-'a']++;

    for(int i=0; i<strlen(s); i++)
      if(hash[s[i]-'a']==1){
        printf("%d\n",i);
        flag = 0;
        break;
      }
    if(flag==1)
      printf("-1\n");
  }
}

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

int main()
{
  int test;
  cin>>test;

  while(test--){

    char s[9999];
    cin>>s;

    int hash[26] = {0}, flag=1;

    for(int i=0; i<strlen(s); i++)
      hash[s[i]-'a']++;

    for(int i=0; i<strlen(s); i++)
      if(hash[s[i]-'a']==1){
        cout<<i<<endl;
        flag = 0;
        break;
      }
    if(flag==1)
      cout<<-1<<endl;
  }
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test-->0){

      String s = sc.next();

      int hash[] = new int[26], flag=1;

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

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

  }
}

for _ in range(int(input())):

	s = input()
	hash = [0] * 26
	flag = 1
	
	for i in range(len(s)):
		hash[ord(s[i]) - ord("a")] += 1

	for i in range(len(s)):
		
		if hash[ord(s[i]) - ord("a")] == 1:
			print(i)
			flag = 0
			break

	if flag:
		print(-1)

[forminator_quiz id="1201"]

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