Minimum Continuous Sub-sequence with two Lists

Question

TargetList and AvailableTagsList are two lists of string. TargetList will contain Distinct string objects.

Input:
TargetList = {"cat", "dog"};
AvailableTagsList = {"cat", "test", "dog", "get", "spain", "south"};
Output: [0, 2] //'cat' in position 0; 'dog' in position 2


Input:
TargetList = {"east", "in", "south"};
AvailableTagsList = {"east", "test", "east", "in", "east", "get", "spain", "south"};
Output: [2, 7] //'east' in position 2; 'in' in position 3; 
              //'south' in position 6 (east in position 4 is not outputted as it is coming after 'in')

Input:
TargetList = {"east", "in", "south"};
AvailableTagsList = {"east", "test", "south"};
Output: [0] //'in' not present in availableTagsList

I store the positions of words where they appear in the AvailableTags into a listMap.

Map<String, List<Integer>> listMap = new HashMap<>();
int counter = 0;
for(String availableItem : AvailableTagsList) 
{
    if(listMap.containsKey(availableItem))
        listMap.get(availableItem).add(counter);
    else 
    {
        List<Integer> temp = new ArrayList<>();
        temp.add(counter);
        listMap.put(availableItem, temp);
    }
    counter++;
}

And I add all element list in listMap to a resultList.

listMap will be like 
"east" - [0,2,4] 
"in" - [3] 
"south" - [7] 

resultList will have like [0,2,4,3,7] 

What I can't wrap my head around with is, using this resultList how do I display the minimum subsequence in the AvailableTagsList? Am I using the right approach? How is my progress so far? Are there any other alternative approaches to solve this problem.

Answer 1

I don't know the optimum solution for this problem but according to your idea

• Get the position of each word from TargetList in the AvailableTagsList (Note that they will be sorted) for example if my target list and available list are : TargetList = {"east", "in", "south"} AvailableTagsList = {"east", "test", "east", "in", "east", "get", "spain", "south"} So after this step I would have east : 0,2,4 in : 3 south: 7
• Now: I know that I can have 3 possible start right? for the first position of my start word p0, can I find a position p1 for word (i+1) such that p1 > p0 ?? if yes, can I have a position p2 for word(i+2) such that p2 > p1 and so on till I find all my target list. How can I do that ? if I know position p1 , I need to find the first p2 such that p2 > p1 ? Can I use binary search to do that ? yes because all the arrays are sorted . So here is the code

public class MinimumCtsSubsequence {

    static String[] words, tags;

    public static void main(String[] args) {
        words = new String[] { "east", "in", "south" };
        tags = new String[] { "east", "test", "east", "in", "east", "get", "spain", "south" };
        ArrayList<Integer> ans = minSubSequence();
        for (int i = 0; i < ans.size(); ++i) {
            System.out.print(ans.get(i) + " ");
        }

    }

    static ArrayList<Integer> minSubSequence() {
        ArrayList<Integer>[] occur = new ArrayList[words.length];
        for (int i = 0; i < words.length; ++i)
            occur[i] = new ArrayList<Integer>();
        HashMap<String, Integer> indices = new HashMap<String, Integer>();
        for (int i = 0; i < words.length; ++i) {
            indices.put(words[i], i);
        }
        for (int i = 0; i < tags.length; ++i) {
            String tag = tags[i];
            if (indices.containsKey(tag)) {
                int wordI = indices.get(tag);
                occur[wordI].add(i);
            }
        }
        // till now comp is o(n)
        // loop throught all the starts that we have
        int ans = Integer.MAX_VALUE;
        int s1 = 0, e1 = 0;
        for (int i = 0; i < occur[0].size(); ++i) {
            int start = occur[0].get(i);
            boolean poss = true;
            int next = 0;
            for (int j = 1; j < words.length; ++j) {
                next = getNextGreater(start, occur[j]);
                if (next == -1) {
                    poss = false;
                    break;
                }
            }
            if (poss && ans > next - start) {
                s1 = start;
                e1 = next;
                ans = next - start;
            }

        }
        ArrayList<Integer> solu = new ArrayList<Integer>();

        if (ans == Integer.MAX_VALUE) {
            solu.add(0);
            return solu;
        }

        solu.add(s1);
        solu.add(e1);

        return solu;
    }

    static int getNextGreater(int x, ArrayList<Integer> arr) {
        int start = 0;
        int end = arr.size() - 1;
        int ans = -1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr.get(mid) <= x) {// go right
                start = mid + 1;
            } else {
                ans = arr.get(mid);
                end = mid;
            }

        }
        if (start == end && arr.get(start) > x)
            return arr.get(start);
        return ans;
    }