Solution for the problem: https://plus.google.com/117081144164759109682/posts/JTUFjMB2Jun

MinWordRegion.java

package code;

public class MinWordRegion {
	public static class Result {
		/** zero-based */
		public int start;
		/** zero-based */
		public int end;
		
		public int length() {
			return end - start + 1;
		}
	}
	

	public static class InputEntry {
		/** zero-based */
		public final int id;
		/** zero-based */
		public final int index;
		
		public InputEntry(int id, int index) {
			this.id = id;
			this.index = index;
		}
	}
	
	int found;
	Result result;
	int start;
	int end;
	InputEntry[] input;
	int totalCount;
	
	void checkResult() {
		if (found == totalCount) {
			int len = input[end].index - input[start].index + 1;
			if (result == null || len < result.length()) {
				if (result == null) {
					result = new Result();
				}
				result.start = input[start].index;
				result.end = input[end].index;
			}
		}
	}
	
	public Result find(InputEntry[] input, int[] counts) {
		this.input = input;
		totalCount = 0;
		for (int i = 0; i < counts.length; i++) {
			totalCount += counts[i];
		}
		
		int[] occur = new int[counts.length];
		
		start = 0;
		end = -1;
		found = 0;
		result = null;
		
		while (start < input.length) {
			
			// move end until all words are found
			while(end + 1 < input.length) {
				end++;
				int id = input[end].id;
				if (id < occur.length) {
					occur[id]++;
					if (occur[id] <= counts[id]) {
						found++;
						assert found <= totalCount;
						if (found == totalCount) {
							break;
						}
					}
				}
			}
			
			// check length
			checkResult();
			
			// move start until not all words are found
			while (start < input.length) {
				int id = input[start].id;
				start++;
				if (id < occur.length) {
					occur[id]--;
					assert occur[id] >= 0;
					if (occur[id] < counts[id]) {
						found--;
						assert found >= 0;
						if (found < totalCount) {
							break;
						}
					}
				}
				
				checkResult();
			}
		}
		
		return result;
	}
}

MinWordRegionTest.java

package code;

import static code.MinWordRegion.*;

import static org.junit.Assert.*;

import org.junit.Test;

public class MinWordRegionTest {
	InputEntry[] input = {
			new InputEntry(0, 1),
			new InputEntry(1, 2),
			new InputEntry(1, 4),
			new InputEntry(2, 5),
			new InputEntry(2, 8),
			new InputEntry(1, 10),
			new InputEntry(0, 11),
 		};

	@Test
	public void TestCase1() {
		int[] counts = {1, 2, 1};
		MinWordRegion algo = new MinWordRegion();
		Result result = algo.find(input, counts);
		assertNotNull(result);
		assertEquals(1, result.start);
		assertEquals(5, result.end);
	}

	@Test
	public void TestCase2() {
		int[] counts = {4, 2};
		MinWordRegion algo = new MinWordRegion();
		Result result = algo.find(input, counts);
		assertNull(result);
	}

	@Test
	public void TestCase3() {
		int[] counts = {1, 1, 1};
		MinWordRegion algo = new MinWordRegion();
		Result result = algo.find(input, counts);
		assertNotNull(result);
		assertEquals(8, result.start);
		assertEquals(11, result.end);
	}

}