Java: Find first non-repeating character from a stream of characters
Java String: Exercise-49 with Solution
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:
Java Code Editor:
Improve this sample solution and post your code through Disqus
Previous: Write a Java program to remove "b" and "ac" from a given string.
Next: Write a Java program to find lexicographic rank of a given string.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://w3resource.com/java-exercises/string/java-string-exercise-49.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics