MaxCommonWindowForStrings.java

/**
 * Author: Varun
 * Date: Apr 20, 2013
 */
 
import java.util.ArrayList;

public class MaxCommonWindowForStrings {
  public static int[][] getContiguousIndicesOfS1InS2(String s1, String s2) {
		int[] s2Indices = new int[26];
		for(int i = 0; i < s2.length(); i++) {
			s2Indices[s2.charAt(i) - 'a'] = i +1;
		}
		
		ArrayList<int[]> indicesOfS1InS2 = new ArrayList<int[]>();
		ArrayList<Integer> curList = new ArrayList<Integer>();
		for(int i = 0; i < s1.length(); i++) {
			if(s2Indices[s1.charAt(i) - 'a'] != 0) {
				curList.add(s2Indices[s1.charAt(i) - 'a'] - 1);
			} else {
				if(!curList.isEmpty()) {
					indicesOfS1InS2.add(toIntArray(curList));
					curList.clear();
				}
			}
		}
		
		if(!curList.isEmpty()) {
			indicesOfS1InS2.add(toIntArray(curList));
			curList.clear();
		}
		
		return toInt2DArray(indicesOfS1InS2);
	}
	
	public static int[][] toInt2DArray(ArrayList<int[]> list) {
		int[][] ret = new int[list.size()][];
		for(int i = 0; i < ret.length; i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}
	
	public static int[] toIntArray(ArrayList<Integer> list) {
		int[] ret = new int[list.size()];
		for(int i = 0; i < ret.length; i++) {
			ret[i] = list.get(i);
		}			
		return ret;
	}
	
	public static int[] getMaxCommonWindow(int[] indicesOfS1InS2, int startIndexOfArray) {
		int maxIndexOfS2 = indicesOfS1InS2[startIndexOfArray];
		int minIndexOfS2 = indicesOfS1InS2[startIndexOfArray];
		int[] maxWindowStartingWithStartIndexOfArray = {startIndexOfArray, startIndexOfArray};
		
		if(startIndexOfArray == indicesOfS1InS2.length - 1) {
			return maxWindowStartingWithStartIndexOfArray;
		}
		
		for(int i = startIndexOfArray + 1; i < indicesOfS1InS2.length; i++) {
			if(indicesOfS1InS2[i] > maxIndexOfS2) {
				maxIndexOfS2 = indicesOfS1InS2[i];
			} else if(indicesOfS1InS2[i] < minIndexOfS2) {
				minIndexOfS2 = indicesOfS1InS2[i];
			}
			
			if((maxIndexOfS2 - minIndexOfS2) == (i - startIndexOfArray)) {
				maxWindowStartingWithStartIndexOfArray[1] = i;
			}
		}
		
		int[] maxWindowNotStartingWithStartIndexOfArray = getMaxCommonWindow(indicesOfS1InS2, startIndexOfArray + 1);
		
		return getGreaterWindow(maxWindowNotStartingWithStartIndexOfArray, maxWindowStartingWithStartIndexOfArray);
	}
	
	public static int[] getGreaterWindow(int[] win1, int[] win2) {
		if((win1[1] - win1[0]) > (win2[1] - win2[0])) {
			return win1;
		}
		return win2;
	}
	
	public static int findMinMax(int[] array, int startIndex, int endIndex, boolean findMin) {
		int ret = array[startIndex];
		for(int i = startIndex; i <= endIndex; i++) {
			if(findMin) {
				if(ret > array[i]) {
					ret = array[i];
				}
			} else {
				if(ret < array[i]) {
					ret = array[i];
				}
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		String s1 = "abclmnoxyz";
		String s2 = "caboxleyzm";
		
		int[][] contiguousIndicesOfS1InS2 = getContiguousIndicesOfS1InS2(s1, s2);
		int[] maxWindow = {0, -1};
		int[] maxContiguousIndicesOfS1InS2 = null;
		for(int[] indicesOfS1InS2 : contiguousIndicesOfS1InS2) {
			int[] window = getMaxCommonWindow(indicesOfS1InS2, 0);
			maxWindow = getGreaterWindow(maxWindow, window);
			if(window == maxWindow) {
				maxContiguousIndicesOfS1InS2 = indicesOfS1InS2;
			}
		}
		
		System.out.print("Substring from S2 = ");
		if(maxWindow[1] - maxWindow[0] < 0) {
			System.out.println("No common window found");
		} else {
			System.out.println(s2.substring(findMinMax(maxContiguousIndicesOfS1InS2, maxWindow[0], maxWindow[1], true), 
					findMinMax(maxContiguousIndicesOfS1InS2, maxWindow[0], maxWindow[1], false) + 1));
		}
	}
}