Write a java program to find first non-repeating character in a string. Given an input string, Write a java code to find first non-repeating character in a string.
For example –
i) Input string – java
Output – j (j is the first non-repeating character)
ii) Input string – web rewrite
Output – b (b is the first non-repeating character)
Find First Non-repeating Character in a String
Let’s first think how do you approach this problem. Which data structure should you use and why?
Find First Non-repeating character in a String using HashMap – Java Code
The simplest solution is to use HashMap to find first non-repeating character in a String. Here is the algorithm to find first non repeating character.
a) Traverse a String and store each character and it’s count in a HashMap.
b) Now, we know each character and it’s count. Let’s traverse a string again and check the count for each character in a Map. Once we found the character with count 1, just break the loop and return that character.
We are traversing the string again from first to the last character as HashMap doesn’t maintain the insertion order.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
/* Find first non-repeating character in a string using hashmap */ import java.util.*; public class FirstNonRepeatedCharacter { /** * @param args the command line arguments */ public static void main(String[] args) { System.out.println("Enter an input string "); // Take an input Scanner in = new Scanner(System.in); String str = in.nextLine(); // Assign length of a string int len = str.length(); // HashMap implementation for key and value pair HashMap<Character, Integer> charcount = new HashMap<Character, Integer>(); Character ch; /*Create a key and value pair for character and it's count. If there is no value stored for a character then set it to 1. Else we increment the character value by 1 */ for(int i = 0; i < len; i++) { ch = str.charAt(i); /* If character is already exists then increment it's count by 1 */ if(charcount.containsKey(ch)) { charcount.put(ch, charcount.get(ch)+1); } else { // If character does not not exist charcount.put(ch, 1); } } for (int j = 0; j < len; j++) { ch = str.charAt(j); // Check character with value 1 (First non-repeated character) if(charcount.get(ch) == 1){ System.out.println("First non-repeated character is " + ch); break; } } } } |
Java Program to Find First Non-repeating character in a String using LinkedHashMap
In this solution, we are going to use LinkedHashMap to store character and it’s count. The advantage of using LinkedHashMap is that it maintains the insertion order. So, once we traversed the string and created the map of a character and it’s count, we just need to iterate through LinkedHashMap again and choose the first entry with a value 1.
1) Traverse a string and create a map for character and it’s count.
2) Loop through LinkedHashMap to find an entry with a value 1.
Programming questions on stack
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.LinkedHashMap; import java.util.Map; import java.util.Map.Entry; import java.util.Scanner; public class FindFirstNonRepeatedCharacter { public static void main(String[] args) { String s; System.out.println("Enter an input string "); Scanner inp = new Scanner(System.in); s = inp.nextLine(); Map<Character, Integer> charCount = new LinkedHashMap<>(); Character ch; for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); /* If key exist then increment it's value otherwise set it's value to 1 */ if (charCount.containsKey(ch)) { charCount.put(ch, charCount.get(ch) + 1); } else { charCount.put(ch, 1); } } //Traverse LinkedHashMap for (Entry<Character, Integer> entry : charCount.entrySet()) { if (entry.getValue() == 1) { System.out.println("First non-repeated character is " + entry.getKey()); break; } } } } |
Programming questions on a linked list
Find First Non-Repeating Character in a String – Video Tutorial
In this video tutorial, I have explained how we can first non-repeating character in a string using HashMap and LinkedHashMap.
Conclusion
I have explained java program to find the first non-repeated character in a string using HashMap and LinkedHashMap. If you know some other efficient way to solve this problem you can let us know through your comments.
