Java практика. Найти первый неповторяющийся символ в строке, выполнив только один обход

Для заданной строки найдите в ней первый неповторяющийся символ, выполнив только один ее обход.

Например,

Input:

string is ABCDBAGHC

Output:

первый неповторяющийся символ: D

Простым решением было бы сохранить количество каждого символа в map или массиве, пройдя его один раз. 

Затем еще раз  просмотреть строку, чтобы найти первый символ, имеющий значение 1. Временная сложность этого решения равна O(n), где n длина входной строки. Проблема с этим решением заключается в том, что строка проходится дважды, что нарушает ограничения программы.

Мы можем решить эту задачу за один обход строки. Идея состоит в том, чтобы использовать map для хранения количества каждого отдельного символа и индекса его первого или последнего вхождения в строку. Затем пройтись по map и найти символ с минимальным индексом строки.

import java.util.HashMap;
import java.util.Map;
 
// Pair class
class Pair<U, V>
{
    public U first;     // первое поле пары
    public V second;    // второе поле пары
 
    // Создает новую пару с указанными значениями
    private Pair(U first, V second)
    {
        this.first = first;
        this.second = second;
    }
 
    // наш метод для создания неизменяемого экземпляра Typed Pair
    public static <U, V> Pair <U, V> of(U a, V b)
    {
        // вызывам приватный конструктор
        return new Pair<>(a, b);
    }
}
 
class Main
{
    // Функция для поиска первого неповторяющегося символа в
    // строке, выполнив только один ее обход
    public static int findNonRepeatingChar(String str)
    {
        // базовый вариант
        if (str == null || str.length() == 0) {
            return -1;
        }
 
        // map для хранения количества символов и индекса их
        // последнее вхождение в строку
        Map<Character, Pair<Integer, Integer>> map = new HashMap<>();
 
        for (int i = 0; i < str.length(); i++)
        {
            map.putIfAbsent(str.charAt(i), Pair.of(0, 0));
            map.get(str.charAt(i)).first++;
            map.get(str.charAt(i)).second = i;
        }
 
        // сохраняет индекс первого неповторяющегося символа
        int min_index = -1;
 
        // пройти по map и найти символ со счетом 1 и
        // минимальный индекс строки
        for (var value: map.values())
        {
            int count = value.first;
            int firstIndex = value.second;
 
            if (count == 1 && (min_index == -1 || firstIndex < min_index)) {
                min_index = firstIndex;
            }
        }
 
        return min_index;
    }
 
    public static void main(String[] args)
    {
        String str = "ABCDBAGHC";
 
        int index = findNonRepeatingChar(str);
        if (index != -1)
        {
            System.out.println("The first non-repeating character in the string is "
                    + str.charAt(index));
        } else {
            System.out.println("первый неповторяющийся символ:");
        }
    }
}

Вывод:
первый неповторяющийся символ: D

Временная сложность этого решения O(n) так как мы делаем один обход строки длины n и один обход map. 

t.me/java – решение задач Java