Given a string, find the first non-repeating character in only one scan

Question

Given the string, find the first non-repeating character in it. For example, if the input string is "GeeksforGeeks", then the output should be "f.

We can use string characters as an index and build an array of count. Below is the algorithm.

1) Scan the line from left to right and build an array of count or HashMap.
2) Again, scan the line from left to right and check the number of each character, if you find an element that counts 1, return it.

Above algorithm from GeeksForGeeks

But this requires two array scans. I want to find the first non-repeating character in only one scan. I implement the above algorithms. Please check it also on Ideone

import java.util.HashMap; import java.util.Scanner; /** * * @author Neelabh */ public class FirstNonRepeatedCharacter { public static void main(String [] args){ Scanner scan=new Scanner(System.in); String string=scan.next(); int len=string.length(); HashMap<Character, Integer> hashMap=new HashMap<Character, Integer>(); //First Scan for(int i = 0; i <len;i++){ char currentCharacter=string.charAt(i); if(!hashMap.containsKey(currentCharacter)){ hashMap.put(currentCharacter, 1); } else{ hashMap.put(currentCharacter, hashMap.get(currentCharacter)+1); } } // Second Scan boolean flag=false; char firstNonRepeatingChar = 0; for(int i=0;i<len;i++){ char c=string.charAt(i); if(hashMap.get(c)==1){ flag=true; firstNonRepeatingChar=c; break; } } if(flag==true) System.out.println("firstNonRepeatingChar is "+firstNonRepeatingChar); else System.out.println("There is no such type of character"); } } 

GeeksforGeeks also offers an efficient method, but I think these are also two scans. Next solution from GeeksForGeeks

 #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; // This is First Scan for (i = 0; *(str+i); i++) { (count[*(str+i)].count)++; // If it 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; //Second Scan 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; } 

Answer 1

You can save 2 arrays: the number of characters and the first occurrence (and fill them both during the first scan). Then a second scan will be unnecessary.

Answer 2

Use String java functions, then you will find a solution in only one loop. An example is shown below.

 import java.util.Scanner; public class firstoccurance { public static void main(String args[]){ char [] a ={'h','h','l','l','o'}; //Scanner sc=new Scanner(System.in); String s=new String(a);//sc.next(); char c; int i; int length=s.length(); for(i=0;i<length;i++) { c=s.charAt(i); if(s.indexOf(c)==s.lastIndexOf(c)) { System.out.println("first non repeating char in a string "+c); break; } else if(i==length-1) { System.out.println("no single char"); } } } } 

Answer 3

In the following solution, I declare one CharCountAndPosition class that stores firstIndex and frequencyOfchar. During the characterwise reading line, firstIndex stores the first character meeting, and Ofchar frequency stores the total number of characters.

We will create an array of step CharCountAndPosition : 1 and initialize it step2 .
When scanning a string, initialize firstIndex and frequencyOfchar for each step3 character.
Now in step4 check the CharCountAndPosition array, find the character with frequency == 1 and at least firstIndex
For all the complexity of the time, O (n + 256), where n is the size of the string. O (n + 256) is equivalent to O (n) since 256 is constant. Please find a solution to this on ideone

 public class FirstNonRepeatedCharacterEfficient { public static void main(String [] args){ // step1: make array of CharCountAndPosition. CharCountAndPosition [] array=new CharCountAndPosition[256]; // step2: Initialize array with object of CharCountAndPosition. for(int i=0;i<256;i++) { array[i]=new CharCountAndPosition(); } Scanner scan=new Scanner(System.in); String str=scan.next(); int len=str.length(); // step 3 for(int i=0;i<len;i++){ char c=str.charAt(i); int index=c-'a'; int frequency=array[index].frequencyOfchar; if(frequency==0) array[index].firstIndex=i; array[index].frequencyOfchar=frequency+1; //System.out.println(c+" "+array[index].frequencyOfchar); } boolean flag=false; int firstPosition=Integer.MAX_VALUE; for(int i=0;i<256;i++){ // Step4 if(array[i].frequencyOfchar==1){ //System.out.println("character="+(char)(i+(int)'a')); if(firstPosition> array[i].firstIndex){ firstPosition=array[i].firstIndex; flag=true; } } } if(flag==true) System.out.println(str.charAt(firstPosition)); else System.out.println("There is no such type of character"); } } class CharCountAndPosition{ int firstIndex; int frequencyOfchar; } 

Answer 4

Solution in javascript using lookup table:

 var sample="It requires two scan of an array I want to find first non repeating character in only one scan"; var sampleArray=sample.split(""); var table=Object.create(null); sampleArray.forEach(function(char,idx){ char=char.toLowerCase(); var pos=table[char]; if(typeof(pos)=="number"){ table[char]=sampleArray.length; //a duplicate found; we'll assign some invalid index value to this entry and discard these characters later return; } table[char]=idx; //index of first occurance of this character }); var uniques=Object.keys(table).filter(function(k){ return table[k]<sampleArray.length; }).map(function(k){ return {key:k,pos:table[k]}; }); uniques.sort(function(a,b){ return a.pos-b.pos; }); uniques.toSource(); //[{key:"q", pos:5}, {key:"u", pos:6}, {key:"d", pos:46}, {key:"p", pos:60}, {key:"g", pos:66}, {key:"h", pos:69}, {key:"l", pos:83}] (uniques.shift()||{}).key; //q 

Answer 5

Following C prog, add a char specific value to 'count' if there was no char before, remove the char specific value from 'count' if there used to be a char. At the end, I get a “count” that has a char specific value indicating what that char is!

 //TO DO: //If multiple unique char occurs, which one is occurred before? //Is is possible to get required values (1,2,4,8,..) till _Z_ and _z_? #include <stdio.h> #define _A_ 1 #define _B_ 2 #define _C_ 4 #define _D_ 8 //And so on till _Z //Same for '_a' to '_z' #define ADDIFNONREP(C) if(count & C) count = count & ~C; else count = count | C; break; char getNonRepChar(char *str) { int i = 0, count = 0; for(i = 0; str[i] != '\0'; i++) { switch(str[i]) { case 'A': ADDIFNONREP(_A_); case 'B': ADDIFNONREP(_B_); case 'C': ADDIFNONREP(_C_); case 'D': ADDIFNONREP(_D_); //And so on //Same for 'a' to 'z' } } switch(count) { case _A_: return 'A'; case _B_: return 'B'; case _C_: return 'C'; case _D_: return 'D'; //And so on //Same for 'a' to 'z' } } int main() { char str[] = "ABCDABC"; char c = getNonRepChar(str); printf("%c\n", c); //Prints D return 0; } 

Answer 6

You can maintain the key queue as they are added to the hash map (you add your key to the queue if you add a new key to the hash map). After scanning the string, you use the queue to get the order of the keys as they are added to the card. This functionality exactly matches the Java OrderedHashMap standard library OrderedHashMap .

Answer 7

Here is my solution to the problem.

Iterate through a string. Check if hashset contains a character. If so, remove it from the array. If not, just add it to the array and hashset.

 NSMutableSet *repeated = [[NSMutableSet alloc] init]; //Hashset NSMutableArray *nonRepeated = [[NSMutableArray alloc] init]; //Array for (int i=0; i<[test length]; i++) { NSString *currentObj = [NSString stringWithFormat:@"%c", [test characterAtIndex:i]]; //No support for primitive data types. if ([repeated containsObject:currentObj]) { [nonRepeated removeObject:currentObj];// in obj-c nothing happens even if nonrepeted in nil continue; } [repeated addObject:currentObj]; [nonRepeated addObject:currentObj]; } NSLog(@"This is the character %@", [nonRepeated objectAtIndex:0]); 

Answer 8

If you can limit yourself to ASCII characters, I would recommend a lookup table instead of a hash table. This search table contains a total of 128 entries.

A possible approach is as follows.

We start with an empty Q queue (can be implemented using linked lists) and a lookup table . For the character ch, T [ch] stores the pointer into the node queue containing the character ch and the index of the first occurrence of ch in the string. Initially, all T entries are NULL .

Each node queue stores the symbol and the first occurrence index, as indicated earlier, and also has a special boolean flag called remove, which indicates that the node has been removed from the queue.

Read the line character by character. If the character i ^th is ch, check to see if T [ch] = NULL . If so, this is the first occurrence of ch in the string. Then add the node for ch containing the index i to the queue.

If T [ch] is not NULL , it is a repeating character. If the node pointed to by T [ch] has already been deleted (ie the "node" flag is set), then nothing needs to be done. Otherwise, remove the node from the queue by manipulating the pointers of the previous and next nodes. Also set the remote node flag to indicate that the node is now deleted. Note that we do not release / delete the node at this point, and do not return T [ch] to NULL .

If we continue like this, the nodes for all duplicate characters will be removed from the queue. The remote flag is used to ensure that no node is removed from the queue twice if the character occurs more than two times.

After the string has been fully processed, the first node of the linked list will contain the character code, as well as the index of the first non-repeating character. The memory can then be freed by iterating over the entries of the lookup table T and freeing any non- NULL entries.

Here is the implementation of C. Here, instead of the remote flag, I set the prev and next pointers of the current node to NULL when it is deleted, and check this to see if the node has already been deleted.

 #include <stdio.h> #include <stdlib.h> struct queue_node { int ch; int index; struct queue_node *prev; struct queue_node *next; }; void print_queue (struct queue_node *head); int main (void) { int i; struct queue_node *lookup_entry[128]; struct queue_node *head; struct queue_node *last; struct queue_node *cur_node, *prev_node, *next_node; char str [] = "GeeksforGeeks"; head = malloc (sizeof (struct queue_node)); last = head; last->prev = last->next = NULL; for (i = 0; i < 128; i++) { lookup_entry[i] = NULL; } for (i = 0; str[i] != '\0'; i++) { cur_node = lookup_entry[str[i]]; if (cur_node != NULL) { /* it is a repeating character */ if (cur_node->prev != NULL) { /* Entry has not been removed. Remove it from the queue. */ prev_node = cur_node->prev; next_node = cur_node->next; prev_node->next = next_node; if (next_node != NULL) { next_node->prev = prev_node; } else { /* Last node was removed */ last = prev_node; } cur_node->prev = NULL; cur_node->next = NULL; /* We will not free the node now. Instead, free * all nodes in a single pass afterwards. */ } } else { /* This is the first occurence - add an entry to the queue */ struct queue_node *newnode = malloc (sizeof(struct queue_node)); newnode->ch = str[i]; newnode->index = i; newnode->prev = last; newnode->next = NULL; last->next = newnode; last = newnode; lookup_entry[str[i]] = newnode; } print_queue (head); } last = head->next; while (last != NULL) { printf ("Non-repeating char: %c at index %d.\n", last->ch, last->index); last = last->next; } /* Free the queue memory */ for (i = 0; i < 128; i++) { if (lookup_entry[i] != NULL) { free (lookup_entry[i]); lookup_entry[i] = NULL; } } free (head); return (0); } void print_queue (struct queue_node *head) { struct queue_node *tmp = head->next; printf ("Queue: "); while (tmp != NULL) { printf ("%c:%d ", tmp->ch, tmp->index); tmp = tmp->next; } printf ("\n"); } 

Answer 9

Instead of making things more complex, I can use three for loops to handle this.

 class test{ public static void main(String args[]){ String s="STRESST";//Your input can be given here. char a[]=new char[s.length()]; for(int i=0;i<s.length();i++){ a[i]=s.charAt(i); } for(int i=0;i<s.length();i++){ int flag=0; for(int j=0;j<s.length();j++){ if(a[i]==a[j]){ flag++; } } if(flag==1){ System.out.println(a[i]+" is not repeated"); break; } } } } 

I think it will be useful for people who just look at the logical part without any complicated methods used in the program.

Answer 10

This can be done in one scan using the substring method. Do it like this:

 String str="your String";<br> String s[]= str.split("");<br> int n=str.length();<br> int i=0;<br><br> for(String ss:s){ if(!str.substring(i+1,n).contains(ss)){ System.out.println(ss); } } 

This will have the lowest complexity and will search for it even without completing one full scan.

Answer 11

Add each character to the HashSet and check if hashset.add () returns true if it returns false and then removes the character from hashset. Then getting the first hash value will give you the first non-repeating character. Algorithm:

  for(i=0;i<str.length;i++) { HashSet hashSet=new HashSet<>() if(!hashSet.add(str[i)) hashSet.remove(str[i]) } hashset.get(0) will give the non repeated character. 

Answer 12

I have this program which is simpler, it does not use data structures

 public static char findFirstNonRepChar(String input){ char currentChar = '\0'; int len = input.length(); for(int i=0;i<len;i++){ currentChar = input.charAt(i); if((i!=0) && (currentChar!=input.charAt(i-1)) && (i==input.lastIndexOf(currentChar))){ return currentChar; } } return currentChar; } 

Answer 13

Simple (non-hashed) version ...

 public static String firstNRC(String s) { String c = ""; while(s.length() > 0) { c = "" + s.charAt(0); if(! s.substring(1).contains(c)) return c; s = s.replace(c, ""); } return ""; } 

or

 public static char firstNRC(String s) { s += " "; for(int i = 0; i < s.length() - 1; i++) if( s.split("" + s.charAt(i)).length == 2 ) return s.charAt(i); return ' '; } 

Answer 14

// This is simple logic for finding the first non-repeating character ....

 public static void main(String[] args) { String s = "GeeksforGeeks"; for (int i = 0; i < s.length(); i++) { char begin = s.charAt(i); String begin1 = String.valueOf(begin); String end = s.substring(0, i) + s.substring(i + 1); if (end.contains(begin1)); else { i = s.length() + 1; System.out.println(begin1); } } } 

Answer 15

 @Test public void testNonRepeadLetter() { assertEquals('f', firstNonRepeatLetter("GeeksforGeeks")); assertEquals('I', firstNonRepeatLetter("teststestsI")); assertEquals('1', firstNonRepeatLetter("123aloalo")); assertEquals('o', firstNonRepeatLetter("o")); } private char firstNonRepeatLetter(String s) { if (s == null || s.isEmpty()) { throw new IllegalArgumentException(s); } Set<Character> set = new LinkedHashSet<>(); for (int i = 0; i < s.length(); i++) { char charAt = s.charAt(i); if (set.contains(charAt)) { set.remove(charAt); } else { set.add(charAt); } } return set.iterator().next(); } 

Answer 16

here is the tested code in java. note that it is possible that a non-duplicate character was not found, and for this we return '0'

 // find first non repeated character in a string static char firstNR( String str){ int i, j, l; char letter; int[] k = new int[100]; j = str.length(); if ( j > 100) return '0'; for (i=0; i< j; i++){ k[i] = 0; } for (i=0; i<j; i++){ for (l=0; l<j; l++){ if (str.charAt(i) == str.charAt(l)) k[i]++; } } for (i=0; i<j; i++){ if (k[i] == 1) return str.charAt(i); } return '0'; 

Answer 17

Search for the first non-repeating character in one pass O (n) without using the indexOf and lastIndexOf methods

 package nee.com; public class FirstNonRepeatedCharacterinOnePass { public static void printFirstNonRepeatedCharacter(String str){ String strToCaps=str.toUpperCase(); char ch[]=strToCaps.toCharArray(); StringBuilder sb=new StringBuilder(); // ASCII range for AZ ( 91-65 =26) boolean b[]=new boolean[26]; for(int i=0;i<ch.length;i++){ if(b[ch[i]-65]==false){ b[ch[i]-65]=true; } else{ //add repeated char to StringBuilder sb.append(ch[i]+""); } } for(int i=0;i<ch.length;i++){ // if char is not there in StringBuilder means it is non repeated if(sb.indexOf(ch[i]+"")==-1){ System.out.println(" first non repeated in lower case ...."+Character.toLowerCase((ch[i]))); break; } } } public static void main(String g[]){ String str="abczdabddcn"; printFirstNonRepeatedCharacter(str); } } 

Answer 18

Here is the logic to find the first non-repeatable letter in String.

 String name = "TestRepeat"; Set <Character> set = new LinkedHashSet<Character>(); List<Character> list = new ArrayList<Character>(); char[] ch = name.toCharArray(); for (char c :ch) { set.add(c); list.add(c); } Iterator<Character> itr1 = set.iterator(); Iterator<Character> itr2= list.iterator(); while(itr1.hasNext()){ int flag =0; Character setNext= itr1.next(); for(int i=0; i<list.size(); i++){ Character listNext= list.get(i); if(listNext.compareTo(setNext)== 0){ flag ++; } } if(flag==1){ System.out.println("Character: "+setNext); break; } } 

Answer 19

it is very easy .... you can do it without a collection in java ..

 public class FirstNonRepeatedString{ public static void main(String args[]) { String input ="GeeksforGeeks"; char process[] = input.toCharArray(); boolean status = false; int index = 0; for (int i = 0; i < process.length; i++) { for (int j = 0; j < process.length; j++) { if (i == j) { continue; } else { if (process[i] == process[j]) { status = false; break; } else { status = true; index = i; } } } if (status) { System.out.println("First non-repeated string is : " + process[index]); break; } } } } 

Answer 20

We can create a LinkedHashMap with each character in the string and the corresponding count. And then go through the map, when you meet a char with a score like 1, return that character. Below is the function for the same.

 private static char findFirstNonRepeatedChar(String string) { LinkedHashMap<Character, Integer> map = new LinkedHashMap<>(); for(int i=0;i< string.length();i++){ if(map.containsKey(string.charAt(i))) map.put(string.charAt(i),map.get(string.charAt(i))+1); else map.put(string.charAt(i),1); } for(Entry<Character,Integer> entry : map.entrySet()){ if(entry.getValue() == 1){ return entry.getKey(); } } return ' '; } 

Answer 21

Single pass solution. I used the associated Hashmap here to keep the insertion order. Therefore, I look through all the characters of the string and save it to Linked HashMap. After that, I go through the Linked Hash card and depending on the fact that the first key will have a value of 1, I will print this key and exit the program.

  import java.util.*; class demo { public static void main(String args[]) { String str="GeekGsQuizk"; HashMap <Character,Integer>hm=new LinkedHashMap<Character,Integer>(); for(int i=0;i<str.length();i++) { if(!hm.containsKey(str.charAt(i))) hm.put(str.charAt(i),1); else hm.put(str.charAt(i),hm.get(str.charAt(i))+1); } for (Character key : hm.keySet()) { if(hm.get(key)==1) { System.out.println(key); System.exit(0) ; } } } } 

Answer 22

I know that this is happening for a year, but I think that if you use LinkedHashMap in your solution instead of using HashMap, you will have a guaranteed order on the received map and you can directly return the key with the corresponding value as 1.

Not sure if this is what you wanted, although you have to iterate over the card (not the line) after you filled it, but only my 2 cents.

Hello,

-Vini

Answer 23

I did the same with a LinkedHashSet. The following is a snippet of code:

 System.out.print("Please enter the string :"); str=sc.nextLine(); if(null==str || str.equals("")) { break; }else { chArr=str.toLowerCase().toCharArray(); set=new LinkedHashSet<Character>(); dupSet=new LinkedHashSet<Character>(); for(char chVal:chArr) { if(set.contains(chVal)) { dupSet.add(chVal); }else { set.add(chVal); } } set.removeAll(dupSet); System.out.println("First unique :"+set.toArray()[0]); } 

Answer 24

Here you can find this question.

For the code of the algorithm below, the link is this link (My implementation with test cases)

Using a linked list in conjunction with hashMap

I have a solution that solves it in O (n) time. One array goes through and O (1) space . Inreality area → O (1) is O (26) space

Algorithm

1) at each visit to the symbol for the first time

Create a node for the associated List (keeping this character). Plug it in at the end of the lnkedList. Add a hashMap entry for the newly added symbol character, the node address in the linked list that was before this symbol. If the character is added to the empty linked list of the null list for vale in the hash map.

2) Now, if you meet the same character again

Remove this item from the linked list using the address stored on the hash map, and now you need to update the item that was after the deleted item, the previous item for it. Make it equal to the previous element of the deleted element.

Difficulty analysis

LinkedlIst add element → O (1)

LinkedlIst → O (1) Removal Element

HashMap → O (1)

space O (1)

pass → one in O (n)

  #include<bits/stdc++.h> using namespace std; typedef struct node { char ch; node *next; }node; char firstNotRepeatingCharacter(string &s) { char ans = '_'; map<char,node*> mp;//hash map atmost may consume O(26) space node *head = NULL;//linkedlist atmost may consume O(26) space node *last;// to append at last in O(1) node *temp1 = NULL; node *temp2 = new node[1]; temp2->ch = '$'; temp2->next = NULL; //This is my one pass of array// for(int i = 0;i < s.size();++i) { //first occurence of character// if(mp.find(s[i]) == mp.end()) { node *temp = new node[1]; temp->ch = s[i]; temp->next = NULL; if(head == NULL) { head = temp; last = temp; mp.insert(make_pair(s[i],temp1)); } else { last->next = temp; mp.insert(make_pair(s[i],last)); last = temp; } } //Repeated occurence// else { node *temp = mp[s[i]]; if(mp[s[i]] != temp2) { if(temp == temp1) { head = head->next; if((head)!=NULL){mp[head->ch] = temp1;} else last = head; mp[s[i]] = temp2; } else if((temp->next) != NULL) { temp->next = temp->next->next; if((temp->next) != NULL){mp[temp->next->ch] = temp;} else last = temp; mp[s[i]] = temp2; } else { ; } } } if(head == NULL){;} else {ans = head->ch;} return ans; } int main() { int T; cin >> T; while(T--) { string str; cin >> str; cout << str << " -> " << firstNotRepeatingCharacter(str)<< endl; } return 0; } 

Answer 25

Only one scan is required.

Uses deque (saves char) and hashmap (saves char -> node). When repeating a char, get the char node in deque using hashmap and remove it from deque (O (1) times), but save the char in hashmap with a node value of zero. peek() gives the 1st unique character.

 [pseudocode] char? findFirstUniqueChar(s): if s == null: throw deque<char>() dq = new hashmap<char, node<char>> chToNodeMap = new for i = 0, i < s.length(), i++: ch = s[i] if !chToNodeMap.hasKey(ch): chToNodeMap[ch] = dq.enqueue(ch) else: chNode = chToNodeMap[ch] if chNode != null: dq.removeNode(chNode) chToNodeMap[ch] = null if dq.isEmpty(): return null return dq.peek() // deque interface deque<T>: node<T> enqueue(T t) bool removeNode(node<T> n) T peek() bool isEmpty() 

Answer 26

The string is checked only once; other checks occur on counters and arrays of the first appearance, which are usually much smaller in size. Or at least a lower approach for cases where the string is much larger than the character set the string is made of.

Here is an example in golang:

 package main import ( "fmt" ) func firstNotRepeatingCharacter(s string) int { counts := make([]int, 256) first := make([]int, 256) // The string is parsed only once for i := len(s) - 1; i >= 0; i-- { counts[s[i]]++ first[s[i]] = i } min := 0 minValue := len(s) + 1 // Now we are parsing counts and first slices for i := 0; i < 256; i++ { if counts[i] == 1 && first[i] < minValue { minValue = first[i] min = i } } return min } func main() { fmt.Println(string(firstNotRepeatingCharacter("fff"))) fmt.Println(string(firstNotRepeatingCharacter("aabbc"))) fmt.Println(string(firstNotRepeatingCharacter("cbbc"))) fmt.Println(string(firstNotRepeatingCharacter("cbabc"))) } 

go playground