How To Find First Repeated And Non-Repeated Character In A String Using java8

Question

I have a working example to find the first repeated and Non-repeated character in a String Using java 7

Below is the working example

public class FindFirstRepeatedAndNonRepeatedChar {
    static void firstRepeatedNonRepeatedChar(String inputString) {

        HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();

        char[] strArray = inputString.toCharArray();

        for (char c : strArray) {
            if (charCountMap.containsKey(c)) {
                charCountMap.put(c, charCountMap.get(c) + 1);
            } else {
                charCountMap.put(c, 1);
            }
        }

        for (char c : strArray) {
            if (charCountMap.get(c) == 1) {
                System.out.println("First Non-Repeated Character In '" + inputString + "' is '" + c + "'");

                break;
            }
        }

        for (char c : strArray) {
            if (charCountMap.get(c) > 1) {
                System.out.println("First Repeated Character In '" + inputString + "' is '" + c + "'");

                break;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the string :");
        String input = sc.next();
        firstRepeatedNonRepeatedChar(input);
    }
}

Can anyone help me on how to refactor the above code using Java8?

Answer 1

With some helpful input, I adapted my answer with less code:

public class FirstRepeat {

    public static void main(String[] args) {
        Map<Character, Long> collect =  "abcsdnvs".chars().mapToObj(i -> (char)i).collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));
        collect.forEach( (x,y) -> System.out.println( "Key: " + x + " Val: " + y));

        Optional<Character> firstNonRepeat = collect.entrySet().stream().filter( (e) -> e.getValue() == 1).map(e -> e.getKey()).findFirst();
        if(firstNonRepeat.isPresent()) {
            System.out.println("First non repeating:" + firstNonRepeat.get());
        }
        Optional<Character> firstRepeat = collect.entrySet().stream().filter( (e) -> e.getValue() > 1).map(e -> e.getKey()).findFirst();
        System.out.println("First repeating:" + firstRepeat.orElse(null));
    }
}

What the above does:

1. Create a stream of Characters: "abcsdnvs".chars().mapToObj(i -> (char)i)
2. Group these characters using a collector: .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));

The grouping is split in 3 different parts:

1. Classifier

As pointed out, I can use Function.identity() for that. The equivalent of x -> x. This means we are grouping by the actual character.

2. mapFactory

We are using LinkedHashMap::new for this. The reason is that we need to preserve the insertion order in order to find the first element. The default implementation uses a HashMap which will not preserve insertion order.

3. Downstream collector

Since we are using a grouping, we need to decide how to collect the grouped elements. In this case, we need the count of occurrences. For this, you can use: Collectors.counting() which will simply sum up how many elements are available of a given character.

The program then prints:

Key: a Val: 1
Key: b Val: 1
Key: c Val: 1
Key: s Val: 2
Key: d Val: 1
Key: n Val: 1
Key: v Val: 1
First non repeating:a
First repeating:s

We are using a stream operation to find the first element (based on the filter):

Optional<Character> firstNonRepeat = collect.entrySet().stream().filter( (e) -> e.getValue() == 1).map(e -> e.getKey()).findFirst();

Where we can stream the grouped elements, filter them by a value of ( >1 for first repeate, ==1 for first non-repeating character). The findFirst method then returns the Element, if such an element is present.

The returned value is an Optional and should be treated safely. As pointed out, you can use isPresent() to check if a value has been found (see first print statement) or use orElse(...) to return a default value instead of throwing an exception (see print statement number 2 where I return null as the default to prevent the Optional to throw an Exception in case no repeated letter were found)

Answer 2

Note that even for conventional, imperative solutions, which are still needed today, Java 8 offers improvements. The following idiom:

if (charCountMap.containsKey(c)) {
    charCountMap.put(c, charCountMap.get(c) + 1);
} else {
    charCountMap.put(c, 1);
}

can be replace with a simple

charCountMap.merge(c, 1, Integer::sum);

This will put the specified value (1), if there is no previous value or evaluate the specified function (here the convenient method reference Integer::sum) with the previous value and the new one, to get the new value to store.

But for this specific task, a HashMap<Character, Integer> is overkill. First, we are not interested in the actual count, all we need to know is whether a character has been encountered, in order to determine whether it has been encountered again, which are just two bits of state. Since chars also have a limited value range, we can easily use a linear mapping rather than hashing. In other words, two BitSets are sufficient:

static void firstRepeatedNonRepeatedChar(String s) {
    if(s.isEmpty()) {
        System.out.println("empty string");
        return;
    }
    BitSet seen=new BitSet(), repeated=new BitSet();
    s.chars().forEachOrdered(c -> (seen.get(c)? repeated: seen).set(c));
    if(repeated.isEmpty()) System.out.println("first unique: "+s.charAt(0));
    else {
        s.chars().filter(repeated::get).findFirst()
                 .ifPresent(c -> System.out.println("first repeated: "+(char)c));
        s.chars().filter(c -> !repeated.get(c)).findFirst()
                 .ifPresent(c -> System.out.println("first unique: "+(char)c));
    }
}

The main task is to iterate over all characters and set the bit in either of the bitsets, seen or repeated, depending on whether it has been encountered before.

Then, if there are no repeated characters, the task is simple. Since then, all characters are unique, the first character is also the first unique character. Otherwise, we simply iterate over the string again, stopping at the first character, whose repeated bit is set/unset to get the first repeated/unique character.

Answer 3

This is just an idea, and maybe overkill, but I liked Holger's answer so I wanted to add that just for completeness.

Based on his answer, I drafted a quick Collector impl that can be used throughout to make this very short.

First the static collector that collects both the first non repeat and the first repeat character as Optionals. It is based on the same logic Holger already pointed out:

public class PairCollector {

    public static 
    Collector<Character, ?, Pair<Optional<Character>,Optional<Character>>> get() {
        return Collector.of(PairCollectorImpl::new, PairCollectorImpl::accumulate,
                            PairCollectorImpl::merge, PairCollectorImpl::finish);
    }

    private static final class PairCollectorImpl {

        private BitSet seen=new BitSet(); 
        private BitSet repeated=new BitSet();
        private StringBuilder builder=new StringBuilder();

        public void accumulate(Character val) {
            builder.append(val);
            (seen.get(val)? repeated: seen).set(val);
        }
        PairCollectorImpl merge(PairCollectorImpl other) {
            builder.append(other.builder);
            repeated.or(other.repeated);
            other.seen.stream().forEach(c -> (seen.get(c)? repeated: seen).set(c));
            return this;
        }
        public Pair<Optional<Character>, Optional<Character>> finish() {
            return Pair.of(
                builder.chars().filter(repeated::get).mapToObj(c -> (char)c).findFirst(),
                builder.chars().filter(c -> !repeated.get(c))
                               .mapToObj(c -> (char)c).findFirst());
        }
    }
}

This way you now have a collector that can handle both within one stream and spits out the result for you, like:

public class FirstRepeat {

    public static void main(String[] args) {

        Pair<Optional<Character>, Optional<Character>> collect = "asdbsjd".chars().mapToObj(c -> (char) c)
                .collect(PairCollector.get());
        collect.getLeft().ifPresent(c -> System.out.println(c));
        collect.getRight().ifPresent(c -> System.out.println(c));

        System.out.println();
        List<Character> toTest = "asdbsjd".chars().mapToObj(c -> (char) c).collect(Collectors.toList());

        Pair<Optional<Character>,Optional<Character>> collect2 = toTest.parallelStream().collect(PairCollector.get());
        collect2.getLeft().ifPresent(c -> System.out.println(c));
        collect2.getRight().ifPresent(c -> System.out.println(c));
    }

}

Which prints:

s
a

s
a

It might be overkill though to write your own collector unless you reuse this over and over everywhere in your code :)

Answer 4

In my opinion previous answers look bit complex, can we try this below, it solves it, let me know what is wrong with it

char findFirstRepeatingCharOfStr(String str) {
    str = str.toLowerCase(); // to avoid any case sensitive issue

    for (int i = 0; i < str.length(); i++) {
      if (str.lastIndexOf(str.charAt(i)) > i) {
        return str.charAt(i);
      }
    }

    return 0; // 0 or null if no char is repeating
  }

For non-repeating simple change if (str.lastIndexOf(str.charAt(i)) == i)

Answer 5

String input = "stackoverflow";
Character nonRepeatChar = input.chars().mapToObj(c -> Character.valueOf((char) c))
                          .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) // Finding the character count
                          .entrySet().stream().sorted(Map.Entry.comparingByValue()) //Sorted by character count value
                          .map(entry -> entry.getKey()).findFirst().get(); //Returning the first value