package amazon_challange;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Question2 {

    public Question2() {
    }

    public void solution() {

        ArrayList<Character> input = new ArrayList<>();
        input.add('a');
        input.add('b');
        input.add('c');
        input.add('d');
        input.add('a');
        input.add('e');
        input.add('f');
        input.add('g');
        input.add('h');
        input.add('i');
        input.add('j');
        input.add('e');
        List<Integer> integers = lengthEachScene(input);
        System.out.println(integers);
    }

    class Tuple implements Comparable<Tuple> {
        int start;
        int end;

        public Tuple(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public void merge(Tuple other) {
            start = Math.min(start, other.start);
            end = Math.max(end, other.end);
        }

        @Override
        public int compareTo(Tuple other) {
            return start - other.start;
        }

        public int size() {
            return end - start + 1;
        }
    }

    public List<Integer> lengthEachScene(List<Character> inputList) {
        int n = inputList.size();
        HashMap<Character, Integer> starts = new HashMap<Character, Integer>();
        HashMap<Character, Integer> ends = new HashMap<Character, Integer>();

        for (int i = 0; i < n; i++) {
            Character c = inputList.get(i);
            if (!starts.containsKey(c)) {
                starts.put(c, i);
            }
            ends.put(c, i);
        }

        ArrayList<Tuple> tuples = new ArrayList<>();

        for (char c : inputList) {
            Tuple curr = new Tuple(starts.get(c), ends.get(c));
            Tuple find = getTuple(tuples, curr);
            if (find == null) tuples.add(curr);
            else find.merge(curr);
        }

        ArrayList<Integer> res = new ArrayList<>();
        for (Tuple t : tuples) res.add(t.size());
        return res;
    }

    public Tuple getTuple(List<Tuple> list, Tuple curr) {
        for (Tuple t : list) {
            if (curr.start <= t.end) return t;
        }

        return null;
    }
}