Создайте карту частот, используя LinkedHashMap<Character, Integer>
, затем итерируйте карту, пока не найдете первую с частотным счетом 1. Вы должны использовать LinkedHashMap
, чтобы при наличии более одного неповторяющегося символа , они будут на карте в том же порядке, что и во входной строке. Построение карты - O (n) (амортизировано), а поиск неповторяющегося символа - O (n) , поэтому общая сложность составляет O (n) .
Еще лучше, используйте Streams для построения LinkedHashMap<Integer, Long>
, где ключом является кодовая точка Unicode. Таким образом, ваше решение может обрабатывать персонажей из дополнительных плоскостей, таких как Emojis. 101
import static java.util.function.Function.identity;
import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;
import java.util.LinkedHashMap;
static String firstNonRepeatingCharacter(String text) {
return text.codePoints().boxed()
.collect(groupingBy(identity(), LinkedHashMap::new, counting()))
.entrySet().stream()
.filter(e -> e.getValue() == 1)
.findFirst()
.map(e -> Character.toString(e.getKey()))
.orElse("");
}
Приведенный выше код требует Java 11+. Для Java 8+ используйте:
.map(e -> new String(new int[] { e.getKey() }, 0, 1))
Тест
System.out.println(firstNonRepeatingCharacter("aabefddbccffaa"));
System.out.println(firstNonRepeatingCharacter("aabefddbccffaae"));
System.out.println(firstNonRepeatingCharacter("aabefddbccffaae?"));
Выход
e
?