public String minWindow(String S, String T) {

if (S.length() == 0 || T.length() == 0) return "";

char[] schars = S.toCharArray();

char[] tchars = T.toCharArray();

int sl = schars.length;

int tl = tchars.length;

int[][] n = new int[tl+1][sl+1];

for (int j=0; j<=sl; j++) n[0][j] = 0;

for (int i=1; i<=tl; i++) n[i][0] = -1;

for (int i=1; i<=tl; i++) {

for (int j=1; j<=sl; j++) {

n[i][j] = Math.max(

(schars[j-1] == tchars[i-1] && n[i-1][j-1] != -1) ? j : -1,

n[i][j-1]

);

}

}

int[] edges = new int[2];

int diff = Integer.MAX_VALUE;

int j = 1;

while (j <= sl && n[tl][j] == -1) j++;

while (j <= sl) {

int lastJ = j;

int i = tl;

while (i > 1 && j > 1) {

i--;

j--;

j = n[i][j];

}

if (i == 1 && j > 0 && diff > lastJ - j + 1) {

edges[0] = j;

edges[1] = lastJ;

diff = lastJ - j + 1;

}

j = lastJ;

while (j <= sl && n[tl][j] == lastJ) j++;

}

return (diff == Integer.MAX_VALUE) ? "" : S.substring(edges[0]-1, edges[1]);

}

/**

public String minWindow2s(String S, String T) {

int[][] dp = new int[2][S.length()];

for (int i = 0; i < S.length(); ++i)

dp[0][i] = S.charAt(i) == T.charAt(0) ? i : -1;

/*At time j when considering T[:j+1],

for (int j = 1; j < T.length(); ++j) {

int last = -1;

Arrays.fill(dp[j & 1], -1);

//Now we would like to calculate the candidate windows

//"dp[j & 1]" for T[:j+1]. 'last' is the last window seen.

for (int i = 0; i < S.length(); ++i) {

if (last >= 0 && S.charAt(i) == T.charAt(j))

dp[j & 1][i] = last;

if (dp[~j & 1][i] >= 0)

last = dp[~j & 1][i];

}

}

//Looking at the window data dp[~T.length & 1],

//choose the smallest length window [s, e].

int start = 0, end = S.length();

for (int e = 0; e < S.length(); ++e) {

int s = dp[~T.length() & 1][e];

if (s >= 0 && e - s < end - start) {

start = s;

end = e;

}

}

return end < S.length() ? S.substring(start, end+1) : "";

}

/**

public String minWindow3(String S, String T) {

int N = S.length();

int[] last = new int[26];

int[][] nxt = new int[N][26];

Arrays.fill(last, -1);

for (int i = N - 1; i >= 0; --i) {

last[S.charAt(i) - 'a'] = i;

for (int k = 0; k < 26; ++k) {

nxt[i][k] = last[k];

}

}

List<int[]> windows = new ArrayList();

for (int i = 0; i < N; ++i) {

if (S.charAt(i) == T.charAt(0))

windows.add(new int[]{i, i});

}

for (int j = 1; j < T.length(); ++j) {

int letterIndex = T.charAt(j) - 'a';

for (int[] window: windows) {

if (window[1] < N-1 && nxt[window[1]+1][letterIndex] >= 0) {

window[1] = nxt[window[1]+1][letterIndex];

}

else {

window[0] = window[1] = -1;

break;

}

}

}

int[] ans = {-1, S.length()};

for (int[] window: windows) {

if (window[0] == -1) break;

if (window[1] - window[0] < ans[1] - ans[0]) {

ans = window;

}

}

return ans[0] >= 0 ? S.substring(ans[0], ans[1] + 1) : "";

}

/**

public String minWindow4(String S, String T) {

int m = T.length(), n = S.length();

int[][] dp = new int[m + 1][n + 1];

for (int j = 0; j <= n; j++) {

dp[0][j] = j + 1;

}

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if (T.charAt(i - 1) == S.charAt(j - 1)) {

dp[i][j] = dp[i - 1][j - 1];

} else {

dp[i][j] = dp[i][j - 1];

}

}

}

int start = 0, len = n + 1;

for (int j = 1; j <= n; j++) {

if (dp[m][j] != 0) {

if (j - dp[m][j] + 1 < len) {

start = dp[m][j] - 1;

len = j - dp[m][j] + 1;

}

}

}

return len == n + 1 ? "" : S.substring(start, start + len);

}

public String minWindow5(String S, String T) {

if (S == null || T == null || T.length() > S.length()) return "";

int lenS = S.length();

int lenT = T.length();

char[] charS = S.toCharArray();

char[] charT = T.toCharArray();

int[][] pos = new int[lenT][lenS];

for (int i=0; i<lenT; i++) {

for (int j=0; j<lenS; j++) {

if (charT[i] == charS[j]) {

pos[i][j] = i == 0 ? j : (j == 0 ? -1 : pos[i-1][j-1]);

} else {

pos[i][j] = j == 0 ? -1 : pos[i][j-1];

}

}

}

int start = -1;

int minSize = Integer.MAX_VALUE;

for (int j=lenS-1; j>=0; j--) {

if (pos[lenT-1][j] == -1) break;

if (j - pos[lenT-1][j] + 1 <= minSize) {

start = pos[lenT-1][j];

minSize = j - pos[lenT-1][j] + 1;

}

}

return start == -1 ? "" : S.substring(start, start + minSize);

}

/**

public String minWindow6(String S, String T) {

int n = S.length(), m = T.length();

int l = 0, r = n;

for (int i = 0; i < n; i++) {

if (S.charAt(i) != T.charAt(0)) continue; // No group of mapping is found, so continue

int k = i + 1;

for (int j = 1; j < m; j++, k++) { // Greedy algorithm to find the greedy mapping

while (k < n && S.charAt(k) != T.charAt(j)) k++;

if (k == n) return (r == n ? "" : S.substring(l, r + 1)); // Link for T[j] does not exist, so return

}

if (k - 1 - i < r - l) { // Update the result substring if one with a smaller length is found

l = i; r = k - 1;

}

}

return (r == n ? "" : S.substring(l, r + 1));

}

/**

public String minWindow7(String S, String T) {

int n = S.length(), m = T.length();

int l = 0, r = n;

int[] p = new int[m];

for (int i = 0; i < n; i++) {

if (S.charAt(i) != T.charAt(0)) continue; // No group of mapping is found, so continue

p[0] = i; // Group of mapping is found, so update the first link

for (int j = 1, k = i + 1; j < m; j++, k++) { // Greedy algorithm to find the greedy mapping

if (k <= p[j]) break; // Early termination, since the remaining links have been computed in previous groups

while (k < n && S.charAt(k) != T.charAt(j)) k++;

if (k == n) return (r == n ? "" : S.substring(l, r + 1)); // Link for T[j] does not exist, so return

p[j] = k; // Else update the link for T[j]

}

if (p[m - 1] - p[0] < r - l) { // Update the result substring if one with a smaller length is found

l = p[0]; r = p[m - 1];

}

}

return (r == n ? "" : S.substring(l, r + 1));

}

public String minWindow8(String S, String T) {

int lenS = S.length();

int lenT = T.length();

char[] charS = S.toCharArray();

char[] charT = T.toCharArray();

int left = 0;

int right = 0;

int flag = 0;

int start = -1;

int minLen = lenS + 1;

while (right < lenS) {

while (left <= lenS - lenT && charS[left] != charT[0]) left++;

if (left > lenS - lenT) break;

right = left;

flag = 0;

while (flag < lenT && right < lenS) {

if (charS[right] == charT[flag]) {

flag++;

}

right++;

}

if (flag != lenT) break;

if (right - left < minLen) {

minLen = right - left;

start = left;

}

left++;

right = left;

}

return start == -1 ? "" : S.substring(start, start + minLen);

}

public String minWindow9(String S, String T) {

int lenS = S.length();

int lenT = T.length();

char[] charS = S.toCharArray();

char[] charT = T.toCharArray();

int left = 0;

int right = 0;

int flag = 0;

int start = -1;

int minLen = lenS + 1;

while (right < lenS) {

while (left <= lenS - lenT && charS[left] != charT[0]) left++;

if (left > lenS - lenT) break;

right = left;

flag = 0;

while (flag < lenT && right < lenS) {

if (charS[right] == charT[flag]) {

flag++;

}

right++;

}

if (flag != lenT) break;

int newStart = backwards(charS, charT, left, right-1);

left = Math.max(left, newStart);

if (right - left < minLen) {

minLen = right - left;

start = left;

}

left++;

right = left;

}

return start == -1 ? "" : S.substring(start, start + minLen);

}

private int backwards(char[] charS, char[] charT, int begin, int end) {

int flagS = end;

int flagT = charT.length - 1;

while (true) {

if (charS[flagS] == charT[flagT]) {

if (flagT == 0) return flagS;

flagT--;

}

flagS--;

}

}