# Simple sliding window solution in Java [Time: O(S*T), Space: O(1)]

• Whenever there is a match between the first character of the String T and the i th character of String S begin searching for the sequence T in S.

``````public String minWindow(String S, String T) {
int l1 = S.length();
int l2 = T.length();
int min = Integer.MAX_VALUE;
int minInd = 0;
for(int i=0;i<l1-l2+1;i++){
if(S.charAt(i)==T.charAt(0)){
int k = i;
int j = 0;
while(k<l1 && j<l2){
if(S.charAt(k++)==T.charAt(j))
j++;
}

if(j==l2 && k-i<min){
min = Math.min(min, k-i);
minInd = i;
}
}
}
return min==Integer.MAX_VALUE?"":S.substring(minInd, minInd+min);
}``````

• It is very clear that the `k` in your `while(k<l1 && j<l2)` can be advanced at most `S - i` times. For maximum, `k = S`, when `i=0`. For minimum, `k = T`, when `i = S-T`. Thus your algorithm runs in approximately `1/2*(S+T)*(S-T)` time. When `T<<S`, it is just `O(S^2)`, and by no means is `O(S*T)`.

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