w3resource

Java String Exercises: Find first non-repeating character from a stream of characters

Java String: Exercise-49 with Solution

Write a Java program to find first non-repeating character from a stream of characters.

Pictorial Presentation:

Java String Exercises: Find first non-repeating character from a stream of characters

Sample Solution-1:

Java Code:

import java.util.*;

public class Main {

public static void main(String[] args) 
{  
  
int MXCHAR = 256;
 
  List < Character > inDLL = new ArrayList < Character > ();
  boolean[] repeatyn = new boolean[MXCHAR];
  String chrstream = "godisgood";
  System.out.println("String: " + chrstream);
  for (int i = 0; i < chrstream.length(); i++) {
   char x = chrstream.charAt(i);
   System.out.println("Reading: " + x);
   if (!repeatyn[x]) {
    if (!(inDLL.contains(x))) {
     inDLL.add(x);
    } else {
     inDLL.remove((Character) x);
     repeatyn[x] = true;
    }
   }
   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:

Flowchart: Java String Exercises - Find first non-repeating character from a stream of characters

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:

Flowchart: Java String Exercises - Find first non-repeating character from a stream of characters
Flowchart: Java String Exercises - Find first non-repeating character from a stream of characters

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?