How will you find out first non-repeating character from a string

Carvia Tech | April 23, 2019 | 2 min read | 55 views


Using Counting Array for storing number of occurrence of each alphabet

We can find the first non-repeating char from a string using the following algorithm in Big O(n) Time

First Pass

We can maintain a counting array for all possible alphabet values (ASCII code 0-128) and keep on counting the position of array based on Ascii value of character. This will be Big O(n) Time Complexity Task where n is number of letters in the string.

Second Pass

Iterate through the counting array and find the first index position where value is exactly 1, and then break. That will give us the ascii code of character that is non repeating.

Java Implementation
String str = "zzzzzbbbccccddehhhhiii";
int[] countingArray = new int[128];
str.chars().forEach(value -> countingArray[value]++);
int nonRepeatingCharAsInt = 0;
for (int i = 0; i < countingArray.length; i++) {
    if (countingArray[i] == 1) {
        nonRepeatingCharAsInt = i;
        break;
    }
}
System.out.println("character = " + Character.valueOf((char) nonRepeatingCharAsInt));

caveats with this approach

  1. We need to know in advance how many distinct characters are present in the input. The above program will only work for ASCII character set (128)

  2. Memory required for storing counting array may be much more if input is UTF-8 because UTF-8 can have upto 232 unique characters

Alternative approach using Java 8
import java.util.LinkedHashMap;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import static java.util.function.Function.identity;

public class NonRepeatingLetter {
    public static void main(String[] args) {
        findFirstNonRepeatingLetter(args[0], System.out::println);
    }
    private static void findFirstNonRepeatingLetter(String s, Consumer callback) {
        s.chars()
                .mapToObj(i -> Character.valueOf((char) i))
                .collect(Collectors.groupingBy(identity(), LinkedHashMap::new, Collectors.counting()))
                .entrySet().stream()
                .filter(entry -> entry.getValue() == 1L)
                .map(entry -> entry.getKey())
                .findFirst().map(c -> {
            callback.accept(c);
            return c;
        });
    }
}

Top articles in this category:
  1. Morgan Stanley Investment Banking Java Interview Questions
  2. Cracking core java interviews - question bank
  3. Goldman Sachs Java Interview Questions for Senior Developer
  4. Top 30 Hibernate and Spring Data JPA interview questions
  5. ION Trading Java Interview Questions
  6. RBS Java Programming Interview Questions
  7. BlackRock Top Java Interview Questions: Investment Banking Domain


Find more on this topic:
Java Interviews image
Java Interviews

Interview - Product Companies, eCommerce Companies, Investment Banking, Healthcare Industry, Service Companies and Startups.

Last updated 1 week ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info