Question: Given a set CHARS of characters and a string INPUT, find the minimum window in INPUT which will contain all the characters in CHARS in complexity O(n).

Ex:
INPUT = "ABBACBAA"
CHARS = "AAB"

Minimum window is "BAA".


Answer:

This algorithm is based on sliding window approach. In this approach, you start from the beginning of the array and move to right. As soon as you have a window, which have all the required elements, try sliding the window to as much right as possible with all the required elements. If current window length is less than min length found till now, update min length.

For Example of your input array is “ABBACBAA” and minimum window should cover characters “AAB” then sliding window will move like this:

Algorithm

Input is the given array and chars is the array of character need to be found.


1) Make an integer array shouldfind[] of len 256 . i-th element of this array will have a the count how many times we need to find element of ASCII value i.
2) Make another array hasfound of 256 elements, which will have the count of required element found till now.
3) Count <= 0
4) While input[i]
. a. If input[i] element is not to be found -> continue
. b. If input[i] element is required => increase count by 1.
. c. If count is length of chars[] array, slide the window as much right as possible.
. d. If current window length is less than min length found till now. Update min length.
5) end

Java Code: 
public class SlidingWindowApproach {
 private static final int MAX = 256;

 public static void main(String[] args) {

  // input is the the array where we need to find the target elements in
  // shortest window
  int[] input = { 'a', 'b', 'e', 'b', 'c', 'a', 'g', 'h' };
  int inputLength = input.length;

  // target is the array to be found in the input array
  int[] target = { 'a', 'b', 'c' };
  int targetLength = target.length;

  // Make an integer array shouldfind[] of length 256 . i-th element of
  // this array will have a the count how many times we need to find
  // element of ASCII value i.
  int[] shouldfind = new int[MAX];

  // Make another array hasfound of 256 elements, which will have the
  // count of required element found till now.
  int[] hasfound = new int[MAX];

  // Count <= 0
  int count = 0;

  // maximum value of window size could be input array length
  int minwindow = inputLength;

  // Checking how many times each character occurred and increased the
  // count of respective character
  for (int i = 0; i < targetLength; i++)
   shouldfind[target[i]] += 1;

  // below is the logic of finding minimum window
  int start = 0;
  int finish = inputLength;
  int j = 0;
  // it will be set if all characters of target found in the input
  boolean flag = false;

  int iteration = 0;
  for (int i = 0; i < inputLength; i++) {
   iteration++;
   if (shouldfind[input[i]] == 0)
    continue;
   hasfound[input[i]] += 1;

   if (shouldfind[input[i]] >= hasfound[input[i]])
    count++;

   // moving window.control will not go into the loop till it finds all
   // elements.
   if (count == targetLength) {
    flag = true;
    while (shouldfind[input[j]] == 0
      || hasfound[input[j]] > shouldfind[input[j]]) {
     if (hasfound[input[j]] > shouldfind[input[j]])
      hasfound[input[j]]--;
     j++;
    }
    // Checking whether new window is less than the existing window
    if (minwindow > (i - j + 1)) {
     minwindow = i - j + 1;
     finish = i;
     start = j;
    }
   }
  }
  if (flag) {
   //giving the count from 0 to n-1
   System.out.println(start + "  " + finish);
  } else {
   System.out.println("target characters are not there in the input");
  }
 }
}


Complexity: If you walk through the code, i and j can traverse at most N steps (where N is input size size) in the worst case, adding to a total of 2N times. Therefore, time complexity is O(N).

Note : This approach can be applied to finding the area with less distance between words where distance is measured words count between words.Just use words in place of characters.