2

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?

7 Answers 7

8

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.

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

  1. 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)

7
  • 1
    @AsteriskNinja see Edit 3 for more detail about the grouping
    – pandaadb
    Sep 16, 2016 at 12:25
  • 2
    Don’t create “Edit 1”, “Edit 2”, etc sections in your answer. Just remove what has turned out to be less useful. Note that while Collectors.summarizingInt(c -> 1) is better than Collectors.toList(), it still is does more work than needed for the task. Consider, e.g. Collectors.counting()
    – Holger
    Sep 16, 2016 at 12:38
  • 1
    @Holger thanks for the input. I updated the answer using Identifiy (i did not know that one yet) and removing the edits that are not necessary. I made the code smaller and used counting (didn't see that one before). I hope it looks better :)
    – pandaadb
    Sep 16, 2016 at 13:02
  • 1
    You are calling get in the Optional for firstRepeat and firstNonRepeat. If the string doesn't have non repeated elements or all the elements are repeated, you are going to get a NoSuchElementException. You can use ifPresent to display the message and use the Optional in a safe way.
    – David SN
    Sep 16, 2016 at 13:23
  • 1
    @DavidSN you are right - I updated the example to use ifPresent and orElse() to showcase 2 different approaches on how to use the Optional
    – pandaadb
    Sep 16, 2016 at 13:38
3

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.

2
  • 1
    I like that solution. You could incorporate that logic into a custom collector implementation and then have all of that in a 1-liner
    – pandaadb
    Sep 16, 2016 at 13:57
  • 1
    I added another answer (did not want to put it in the first since I don't think it is the best solution) just as a general idea. I think it might be overkill and I think my collector impl could be improved as well
    – pandaadb
    Sep 16, 2016 at 14:12
1

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 :)

6
  • @Holger thanks for your comment - I updated the code. I think (hope) it is correct now. It was in deed very broken. However I don't think I can get around storing the original String in the collector, because using it multithreaded, there is no way (that I can think of) to merge 2 Stringbuilders that track characters without an index. If it is possible, I'd like to know about it :)
    – pandaadb
    Sep 16, 2016 at 14:58
  • @Holger that is perfectly fine - I am fairly new to writing collectors and am happy for any help
    – pandaadb
    Sep 16, 2016 at 15:03
  • 1
    It’s usually best to separate the container type from the Collector interface implementation, to avoid accidentally accessing the wrong instance. The conclusion is that you only need to implement the container type and let Collector.of return an interface implementation. Further, combiner for ordering dependent collectors usually work best when merging into the left container. Besides that, it’s good to know that BitSet also supports streaming and you don’t need a String for invoking chars(); every CharSequence, including StringBuilder has that method.
    – Holger
    Sep 16, 2016 at 15:14
  • 2
    Yes, if the stream has an ordering in the first place (as CharSequence or List sources have), it will merge partial results in the correct order. That’s why Collectors.toList() works. See here.
    – Holger
    Sep 16, 2016 at 15:28
  • 2
    By the way, having that container type, you can also perform the operation without boxing. First, add an overload: public void accumulate(int val) { builder.append((char)val); (seen.get(val)? repeated: seen).set(val); } to PairCollectorImpl, then provide a method like: public static Pair<Optional<Character>, Optional<Character>> get(CharSequence source) { return source.chars() .collect(PairCollectorImpl::new, PairCollectorImpl::accumulate, PairCollectorImpl::merge) .finish(); } in the outer class.
    – Holger
    Sep 16, 2016 at 15:33
1

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)

0
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
0
Character firstNonRepeatedChar =input.trim()
             .toLowerCase()
             .chars()
             .mapToObj(i->(char)i).collect(Collectors.groupingBy(Function.identity(),LinkedHashMap::new, Collectors.counting()))
             .entrySet()
             .stream()
             .filter(i->i.getValue()==1).map(Map.Entry::getKey)
             .collect(Collectors.toList()).get(0);
1
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Nov 6, 2023 at 9:25
0
String input = "asdfaghjklkjhgfdsa";

//find first repeated char in string

input.chars().mapToObj(i-> Character.toLowerCase(Character.valueOf((char) i)))
     .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting())) //count frequency of char 
     .entrySet().stream().filter(entry -> entry.getValue() > 1)
     .map(entry -> entry.getKey())
     .findFirst().get();

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.