# Java Easy O(S*T) time(40ms) Solution

• Java Optimal Solution(40 ms)

``````class Solution {
public String minWindow(String S, String T) {
int min=-1,idx=-1,slen=S.length(),tlen=T.length();
char[] Tc=T.toCharArray();
char[] Sc= S.toCharArray();
int[][] dp= new int[slen][26];

for(int i=slen-2;i>=0;i--){
for(int j=0;j<26;j++){
if(Sc[i+1]== j+'a') dp[i][j]=i+1;
else dp[i][j]=dp[i+1][j];
}
}

for(int i=0;i<slen;i++){
if(Sc[i]!=Tc[0]) continue;
int len= helper(dp,Tc,i);
if(len==-1) break;
if(min==-1 || len<min){
idx=i;
min=len;
}
}
if(min==-1) return "";
return S.substring(idx,idx+min);
}

public int helper(int[][] dp,char[] Tc, int pos){
int i=1;
int start=pos;
for(;i<Tc.length;i++){
if(dp[pos][Tc[i]-'a']==0) break;
else pos= dp[pos][Tc[i]-'a'];
}
if(i==Tc.length) return pos-start+1;
else return -1;
}
}
``````

Java BruteForce Solution

``````class Solution {
public String minWindow(String S, String T) {
int min=-1,idx=-1;
char[] Tc=T.toCharArray();
char[] Sc=S.toCharArray();
for(int i=0;i<S.length();i++){
int len=check(Tc,Sc,i);
if(len<=0) break;
if(min==-1 || len<min){
idx=i;
min=len;
}
}
if(min==-1) return "";
return S.substring(idx,idx+min);
}

public int check(char[] Tc,char[] Sc, int start){
int i=start,j=0;
while(i<Sc.length && j<Tc.length){
if(Sc[i]==Tc[j]) j++;
i++;
}
if(j==Tc.length) return i-start;
return -1;
}
}
``````

• Typical dp solution is O(SxTxlog(S)), this brutal force is O(S^2). It will perform badly when S >> T.

• @derek3 I have added a O(S*T) solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.