class Main {
    static void main(String[] args) {

    }

    /*
       * Użycie LinkedHashMap do znalezienia pierwszego niepowtarzającego się znaku w String
       * Algorytm:
       * 1) stwórz tablicę znaków i iteruj ją aby stworzyć mapę z znakami i ich ilościami
       * 2) iteruj przez LinkedHashMap aby znalezć elementy z wartością 1 - jeśli znajdziesz, to jest rozwiązanie (LinkedHashMap pilnuje porządku wstawiania)
    */

    public static char getFirstNonRepeatedChar1(String str) {
        Map<Character, Integer> counts = new LinkedHashMap<>(str.length());

        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }

        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }

        throw new RuntimeException("String nie zawiera niepowtarzających się znaków.");
    }

    /*
       * Znajduje pierwszy niepowtarzalny znak w String'u w jednym podejściu.
       * Używa dwóch struktur aby ściąć jedną iterację (deal: miejsce w pamięci vs czas).
       * W momencie kiedy używamy struktur do zachowywania powtarzających i niepowtarzających
       * się elementów to na koniec iteracji pierwszy element na liście jest naszym rozwiązaniem,
     */

    public static char firstNonRepeatingChar2(String word) {
        Set<Character> repeating = new HashSet<>();
        List<Character> nonRepeating = new ArrayList<>();

        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);

            if (repeating.contains(letter)) {
                continue;
            }

            if (nonRepeating.contains(letter)) {
                nonRepeating.remove((Character) letter); repeating.add(letter);
            } else {
                nonRepeating.add(letter);
            }
        }

        return nonRepeating.get(0);
    }
}