A quick and practical guide to finding the first non repeated character from a string. Programs on Single traversal O(1) and complete traversal.
1. Overview
In this article, We will be learning and understanding the various ways to find the first non repeated character in a given string in various ways along with Java 8 Streams. Many programs may face this type of question in programming interviews or face to face round.
Let us start with the simple approach and next discover the partial and single iteration through the string.
2. Using HashMap
Steps:
A) Create a Map instanceB) Convert string to char array
C) Looping char array and putting into map each char as key and value as 1 if the key null in the map. The Key is null in the map means that char does not present on the map.
D) If the key is present, then get the existing value from the map and increment by 1.
F) Retrive the entries from map using entrySet() method.
G) Loop through the entries set and get each value of entry object. If the value is 1 then that char has appeared only once in the string.
package com.java.w3schools.blog.java.program.to.strings;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
* Java Program To Find First Non-Repeated Character In String
*
* @author JavaProgramTo.com
*
*/
public class StringnonRepeatedProgram {
public static void main(String[] args) {
withHashMap("abcdabd");
}
/**
* Using hashmap to store the each char as key and its count as value in it.
*
* @param value
*/
private static void withHashMap(String value) {
// Creating map instnace
Map countsByChar = new HashMap<>();
// converting string to char array
char[] chars = value.toCharArray();
//
for (char c : chars) {
if (countsByChar.get(c) == null) {
countsByChar.put(c, 1);
} else {
countsByChar.put(c, countsByChar.get(c) + 1);
}
}
boolean found = false;
for (Entry entry : countsByChar.entrySet()) {
if (entry.getValue() == 1) {
System.out.println("First non repeated char : " + entry.getKey());
found = true;
}
}
if (!found) {
System.out.println("No non repeating char");
}
}
}
Output:
First non repeated char : c
3. Using LinkedHashMap
LinkedHashMap preserves the order they have inserted but whereas HashMap does not. In the above approach, if the input string has two non repeated characters then any of those two will be printed. But the below program works for all types of valid inputs.
/**
* Using LinkedHashMap to store the each char as key and its count as value in it.
*
* @param value
*/
private static void withlinkedHashMap(String value) {
// Creating map instnace
Map countsByChar = new LinkedHashMap<>();
// converting string to char array
char[] chars = value.toCharArray();
//
for (char c : chars) {
if (!countsByChar.containsKey(c)) {
countsByChar.put(c, 1);
} else {
countsByChar.put(c, countsByChar.get(c) + 1);
}
}
boolean found = false;
for (Entry entry : countsByChar.entrySet()) {
if (entry.getValue() == 1) {
System.out.println("First non repeated char : " + entry.getKey());
found = true;
}
}
if (!found) {
System.out.println("No non repeating char");
}
}
4. Using single traversal (Optimized)
In this single traversal approach, we will use an integer array with size 256. the character set is having 256 ASCII codes called 256 charset that uses 16-bit memory representation. int[] array will be initialized with -1 at all indexes such as from 0 to 255. This int array will be used to store the index of the value.
ASCII Table
package com.java.w3schools.blog.java.program.to.strings;
public class NonRepeatedSingleTraversal {
private static final int EXTENDED_ASCII_CODES_COUNT = 256;
public static void main(String[] args) {
String s = "welcome to javaprogramto.com blog w3schools";
int[] indexes = new int[EXTENDED_ASCII_CODES_COUNT];
// setting defalut value to -1 for each index.
for (int i = 0; i < EXTENDED_ASCII_CODES_COUNT; i++) {
indexes[i] = -1;
}
// converting string to char[]
char[] chars = s.toCharArray();
// iterating char array
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
// checking for first occurance of char.
if (indexes[ch] == -1) {
indexes[ch] = i;
} else {
// this will get executed if and if only char is repeated.
indexes[ch] = -i;
}
}
int pos = Integer.MAX_VALUE;
for (int i = 0; i < EXTENDED_ASCII_CODES_COUNT; i++) {
if (indexes[i] >= 0) {
pos = Math.min(pos, indexes[i]);
}
}
System.out.println("first non repeated char is : " + chars[pos]);
}
}
Output:
first non repeated char is : j
This program works as long as the input string has the 256 chars. If any character is out of 256 characters then int[] index will throw java.lang.ArrayIndexOutOfBoundsException. If the string has a heart symbol like this then we need to use another implementation based upon java 8 methods codepoints() instead of chars() method and codepoint() instead of charAt() method.
5. LinkedHashMap with java 8 compute method
The below example is similar to section 3 but here we have used java 8 new collection api method compute(). This simplifies the logic insertion and updates the key on the map. LinkedHashMap retains the insertion order so we always the first non repeated char.
public char firstNonRepeatedCharacter(String str) {
Map chars = new LinkedHashMap<>();
// or use for(char ch: str.toCharArray()) { ... }
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
chars.compute(ch, (k, v) -> (v == null) ? 1 : ++v);
}
for (Map.Entry entry: chars.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return Character.MIN_VALUE;
}
6. Using Java 8 Streams
This is the most simplified code for this problem statement and which supports all characters such as ASCII, 16-bit Unicode and Unicode surrogate pairs.
Java 8 Streams
public static String firstNonRepeatedCharacterJava8(String input) {
Map chars = input.codePoints().mapToObj(cp -> cp)
.collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));
int pos = chars.entrySet().stream().filter(e -> e.getValue() == 1L).findFirst().map(Map.Entry::getKey)
.orElse(Integer.valueOf(Character.MIN_VALUE));
return String.valueOf(Character.toChars(pos));
}
Stream api filter() method understanding is needed. Article here on Stream filter api
7. Conclusion
In this article, we have seen how to find the first non repeated char in string. Shown the code in 5 ways to find the non repeated char using HashMap, LinkedHashmap, single traversal, java 8 compute() method and java 8 streams api.
And also we can find the same using ArrayList and Hashset.
References
ASCII Table
http://www.asciitable.com/
COMMENTS