Saturday, July 23, 2016

Find longest sublist of distinct words

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.junit.Assert;

public class LongestDistinctWords {
    public static void main(String[] args) {

        List<String> resultA = new LongestDistinctWords().occurences(new ArrayList<String>());
        System.err.println("resultA:"+resultA);
        Assert.assertEquals(resultA, Arrays.asList());
        
        List<String> resultB = new LongestDistinctWords().occurences(Arrays.asList("My","My","House","House","Time","Time","Time","Jeep","Jeep","Jeep","Jeep","Jeep","Jeep","Jeep","Jeep","Cat"));
        System.err.println("resultB:"+resultB);
        Assert.assertEquals(resultB, Arrays.asList("My","House"));
        
        List<String> resultC = new LongestDistinctWords().occurences(Arrays.asList("My","Test","My","My","Test","My","Hello","Dog","Hello"));
        System.err.println("resultC:"+resultC);
        Assert.assertEquals(resultC, Arrays.asList("Test""My""Hello""Dog"));
        
        List<String> resultD = new LongestDistinctWords().occurences(Arrays.asList("My","Test","My","Test","Hello","My","Test","Hello","Dog"));
        System.err.println("resultD:"+resultD);
        Assert.assertEquals(resultD, Arrays.asList("My","Test","Hello","Dog"));

        List<String> resultE = new LongestDistinctWords().occurences(Arrays.asList("My","My","And","My","And","My","Hi","How","Are","Hi","Yes","We"));
        System.err.println("resultE:"+resultE);
        Assert.assertEquals(resultE, Arrays.asList("And","My","Hi","How","Are"));

        List<String> resultF = new LongestDistinctWords().occurences(Arrays.asList("My","My","And","My","And","My","Hi","How","Are","Hi","My","We","Can","See"));
        System.err.println("resultF:"+resultF);
        Assert.assertEquals(resultF, Arrays.asList("How","Are","Hi","My","We","Can","See"));
    }
    
    /**
     * Find longest sublist of distinct words
     * @param words
     * @return
     */

    public List<String> occurences(List<String> words) {
        Integer longestStart = 0;
        Integer longestEnd = 0;
        Map<String, Integer> indexAfterWordLastSeenMap = new HashMap<String, Integer>();
        Integer currentStart = 0;
        Integer currentEnd = 0;
        for(String word: words) {
            Integer lastSeen = indexAfterWordLastSeenMap.get(word);
            if(lastSeen != null && lastSeen > currentStart) {
                if(currentEnd - currentStart > longestEnd - longestStart) {
                    longestStart = currentStart;
                    longestEnd = currentEnd;
                }
                currentStart = lastSeen;
            } 
            currentEnd++;
            indexAfterWordLastSeenMap.put(word, currentEnd);
        }
        if(currentEnd - currentStart > longestEnd - longestStart) {
            longestStart = currentStart;
            longestEnd = currentEnd;
        }
        return words.subList(longestStart, longestEnd);
    }
}

No comments:

Post a Comment