$show=/label

Java Program To Find First Non-Repeated Character In String (5 ways)

SHARE:

A quick and practical guide to finding the first non repeated character from a string. Programs on Single traversal O(1) and complete or partial traversals in 5 ways.

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.

Java Program To Find First Non-Repeated Character In String (5 ways)


2. Using HashMap

Steps:

A) Create a Map instance
B) 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

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,16,Arrays,7,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,5,Collections,22,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,81,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,4,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,3,Fast,1,Files,9,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,29,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,Java 8,66,Java 8 Difference,2,Java 8 Stream Conversions,2,java 8 Stream Examples,3,Java 9,1,Java Conversions,11,Java Design Patterns,1,Java Files,1,Java Program,2,Java Programs,65,java.lang,5,java.util. function,1,jQuery,1,Kotlin,10,Kotlin Conversions,3,Kotlin Programs,6,Lambda,1,lang,29,Leap Year,1,live updates,1,Logging,1,Mac OS,2,Math,1,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,1,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,21,String,58,String Programs,9,String Revese,1,Swing,1,System,1,Tags,1,Threads,10,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,2,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program To Find First Non-Repeated Character In String (5 ways)
Java Program To Find First Non-Repeated Character In String (5 ways)
A quick and practical guide to finding the first non repeated character from a string. Programs on Single traversal O(1) and complete or partial traversals in 5 ways.
https://1.bp.blogspot.com/-MqHUAqR9KPw/XmKfwhjIA-I/AAAAAAAACTA/SiPYEmt6QBMeKW0ZExR-2rG0EQAO3vZuQCLcBGAsYHQ/s640/Java%2BProgram%2BTo%2BFind%2BFirst%2BNon-Repeated%2BCharacter%2BIn%2BString%2B%25285%2Bways%2529.png
https://1.bp.blogspot.com/-MqHUAqR9KPw/XmKfwhjIA-I/AAAAAAAACTA/SiPYEmt6QBMeKW0ZExR-2rG0EQAO3vZuQCLcBGAsYHQ/s72-c/Java%2BProgram%2BTo%2BFind%2BFirst%2BNon-Repeated%2BCharacter%2BIn%2BString%2B%25285%2Bways%2529.png
JavaProgramTo.com
https://www.javaprogramto.com/2020/03/java-find-fist-non-repeated-character.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2020/03/java-find-fist-non-repeated-character.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content