Java: Find first non-repeating character from a stream of characters
49. First Non-Repeating in Stream
Write a Java program to find the first non-repeating character from a stream of characters.
Visual Presentation:
Sample Solution-1:
Java Code:
// Importing necessary Java utilities.
import java.util.*;
// Define a class named Main.
public class Main {
// Main method to execute the program.
public static void main(String[] args) {
// Define the maximum number of characters.
int MXCHAR = 256;
// Create a list to store characters in a doubly linked list.
List inDLL = new ArrayList();
// Create a boolean array to check if a character is repeated.
boolean[] repeatyn = new boolean[MXCHAR];
// Define the input string.
String chrstream = "godisgood";
System.out.println("String: " + chrstream);
// Loop through each character in the input string.
for (int i = 0; i < chrstream.length(); i++) {
// Get the character at the current index.
char x = chrstream.charAt(i);
System.out.println("Reading: " + x);
// Check if the character is non-repeating.
if (!repeatyn[x]) {
// If the character is not repeated yet.
if (!(inDLL.contains(x))) {
inDLL.add(x); // Add the character to the list.
} else {
// If the character is already in the list, remove it and mark it as repeated.
inDLL.remove((Character) x);
repeatyn[x] = true;
}
}
// Display the first non-repeating character encountered so far.
if (inDLL.size() != 0) {
System.out.print("The first non-repeating character so far is: ");
System.out.println(inDLL.get(0));
}
}
}
}
Sample Output:
String: godisgood Reading: g The first non-repeating character so far is: g Reading: o The first non-repeating character so far is: g Reading: d The first non-repeating character so far is: g Reading: i The first non-repeating character so far is: g Reading: s The first non-repeating character so far is: g Reading: g The first non-repeating character so far is: o Reading: o The first non-repeating character so far is: d Reading: o The first non-repeating character so far is: d Reading: d The first non-repeating character so far is: i
Flowchart:
Sample Solution-2:
Main.java Code:
//MIT License: https://bit.ly/35gZLa3
import java.util.concurrent.TimeUnit;
public class Main {
private static final String TEXT = "My high school, the Illinois Mathematics and Science Academy, "
+ "showed me that anything is possible and that you're never too young to think big. "
+ "At 15, I worked as a computer programmer at the Fermi National Accelerator Laboratory, "
+ "or Fermilab. After graduating, I attended Stanford for a degree in economics and "
+ "computer science.";
// Ӝ -> Unicode: \u04DC, Code Point: 1244
// 💕 -> Unicode: \uD83D\uDC95, Code Point: 128149
private static final String TEXT_CP = "😍 💕 I Ӝ love you Ӝ so much 😍";
public static void main(String[] args) {
System.out.println("Input text: \n" + TEXT + "\n");
System.out.println("\n\nASCII or 16 bits Unicode characters (less than 65,535 (0xFFFF)) examples:\n");
System.out.println("Loop and break solution:");
long startTimeV1 = System.nanoTime();
char firstcharV1 = Strings.firstNonRepeatedCharacterV1(TEXT);
displayExecutionTime(System.nanoTime() - startTimeV1);
System.out.println("Found character: " + firstcharV1);
System.out.println();
System.out.println(" 256 ASCII codes solution:");
long startTimeV2 = System.nanoTime();
char firstcharV2 = Strings.firstNonRepeatedCharacterV2(TEXT);
displayExecutionTime(System.nanoTime() - startTimeV2);
System.out.println("Found character: " + firstcharV2);
System.out.println();
System.out.println("LinkedHashMap based solution:");
long startTimeV3 = System.nanoTime();
char firstcharV3 = Strings.firstNonRepeatedCharacterV3(TEXT);
displayExecutionTime(System.nanoTime() - startTimeV3);
System.out.println("Found character: " + firstcharV3);
System.out.println();
System.out.println("Java 8, functional-style solution:");
long startTimeV4 = System.nanoTime();
char firstcharV4 = Strings.firstNonRepeatedCharacterV4(TEXT);
displayExecutionTime(System.nanoTime() - startTimeV4);
System.out.println("Found character: " + firstcharV4);
System.out.println("\n---------------------------------------------\n");
System.out.println("Input text: \n" + TEXT_CP + "\n");
System.out.println("\n\nIncluding Unicode surrogate pairs examples:\n");
System.out.println();
System.out.println("Java 8, functional-style solution:");
long startTimeV5 = System.nanoTime();
String firstcharV5 = Strings.firstNonRepeatedCharacterVCP4(TEXT_CP);
displayExecutionTime(System.nanoTime() - startTimeV5);
System.out.println("Found character: " + firstcharV5);
}
private static void displayExecutionTime(long time) {
System.out.println("Execution time: " + time + " ns" + " ("
+ TimeUnit.MILLISECONDS.convert(time, TimeUnit.NANOSECONDS) + " ms)");
}
}
Strings.java Code:
//MIT License: https://bit.ly/35gZLa3
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public final class Strings {
// http://www.alansofficespace.com/unicode/unicd99.htm
private static final int EXTENDED_ASCII_CODES = 256; // can be increased to 65535
private Strings() {
throw new AssertionError("Cannot be instantiated");
}
public static char firstNonRepeatedCharacterV1(String str) {
if (str == null || str.isEmpty()) {
// or throw IllegalArgumentException
return Character.MIN_VALUE;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
int count = 0;
for (int j = 0; j < str.length(); j++) {
if (ch == str.charAt(j) && i != j) {
count++;
break;
}
}
if (count == 0) {
return ch;
}
}
return Character.MIN_VALUE;
}
public static char firstNonRepeatedCharacterV2(String str) {
if (str == null || str.isEmpty()) {
// or throw IllegalArgumentException
return Character.MIN_VALUE;
}
int[] flags = new int[EXTENDED_ASCII_CODES];
for (int i = 0; i < flags.length; i++) {
flags[i] = -1;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (flags[ch] == -1) {
flags[ch] = i;
} else {
flags[ch] = -2;
}
}
int position = Integer.MAX_VALUE;
for (int i = 0; i < EXTENDED_ASCII_CODES; i++) {
if (flags[i] >= 0) {
position = Math.min(position, flags[i]);
}
}
return position == Integer.MAX_VALUE ? Character.MIN_VALUE : str.charAt(position);
}
public static char firstNonRepeatedCharacterV3(String str) {
if (str == null || str.isEmpty()) {
// or throw IllegalArgumentException
return Character.MIN_VALUE;
}
Map<Character, Integer> 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<Character, Integer> entry : chars.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return Character.MIN_VALUE;
}
public static char firstNonRepeatedCharacterV4(String str) {
if (str == null || str.isEmpty()) {
// or throw IllegalArgumentException
return Character.MIN_VALUE;
}
Map<Integer, Long> chs = str.chars()
.mapToObj(cp -> cp)
.collect(Collectors.groupingBy(Function.identity(),
LinkedHashMap::new, Collectors.counting()));
return (char) (int) chs.entrySet().stream()
.filter(e -> e.getValue() == 1L)
.findFirst()
.map(Map.Entry::getKey)
.orElse(Integer.valueOf(Character.MIN_VALUE));
}
public static String firstNonRepeatedCharacterVCP4(String str) {
if (str == null || str.isEmpty()) {
// or throw IllegalArgumentException
return String.valueOf(Character.MIN_VALUE);
}
Map<Integer, Long> chs = str.codePoints()
.mapToObj(cp -> cp)
.collect(Collectors.groupingBy(Function.identity(),
LinkedHashMap::new, Collectors.counting()));
int cp = chs.entrySet().stream()
.filter(e -> e.getValue() == 1L)
.findFirst()
.map(Map.Entry::getKey)
.orElse(Integer.valueOf(Character.MIN_VALUE));
return String.valueOf(Character.toChars(cp));
}
}
Sample Output:
Input text: My high school, the Illinois Mathematics and Science Academy, showed me that anything is possible and that you're never too young to think big. At 15, I worked as a computer programmer at the Fermi National Accelerator Laboratory, or Fermilab. After graduating, I attended Stanford for a degree in economics and computer science. ASCII or 16 bits Unicode characters (less than 65,535 (0xFFFF)) examples: Loop and break solution: Execution time: 1131059 ns (1 ms) Found character: ' 256 ASCII codes solution: Execution time: 308287 ns (0 ms) Found character: ' LinkedHashMap based solution: Execution time: 107942151 ns (107 ms) Found character: ' Java 8, functional-style solution: Execution time: 113887844 ns (113 ms) Found character: ' --------------------------------------------- Input text: 😍 💕 I Ӝ love you Ӝ so much 😍 Including Unicode surrogate pairs examples: Java 8, functional-style solution: Execution time: 2653555 ns (2 ms) Found character: 💕
Flowchart:
For more Practice: Solve these Related Problems:
- Write a Java program to process a stream of characters and output the first non-repeating character after each new input.
- Write a Java program to continuously read characters from input and display the first non-repeating character at each step.
- Write a Java program to simulate a real-time stream of characters and update the first unique character dynamically.
- Write a Java program to process an input stream character by character, maintaining and printing the first non-repeating character encountered so far.
Go to:
PREV : Remove 'b' and 'ac' from String.
NEXT : Lexicographic Rank of String.
Java Code Editor:
Improve this sample solution and post your code through Disqus
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.