Tuesday, February 17, 2015

How will you find out first non-repeating character from a string ? For example, String input = "aaabbbeggh", answer should be 'e'

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 op 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.

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));
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;
        });
    }
}

This question is covered in my eBook - Cracking Java Interviews (Java 8, Hibernate & Spring)

No comments:

Post a Comment

Your comment will be published after review from moderator