Finding shortest possible substring that contains a String

Viewed 2647

This was a question asked in a recent programming interview.

Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T. Say,

S='adobecodebanc' 
T='abc' 
Answer='banc'

I've come up with a solution,

public static String completeSubstring(String T, String S){

        String minSub = T;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <T.length()-1; i++) {
            for (int j = i + 1; j <= T.length() ; j++) {
                String sub = T.substring(i,j);
                if(stringContains(sub, S)){
                    if(sub.length() < minSub.length()) minSub = sub;
                }
            }
        }
        return minSub;

    }
    private static boolean stringContains(String t, String s){
        //if(t.length() <= s.length()) return false;

        int[] arr = new int[256];

        for (int i = 0; i <t.length() ; i++) {
            char c = t.charAt(i);
            arr[c -'a'] = 1;
        }
        boolean found = true;
        for (int i = 0; i <s.length() ; i++) {
            char c = s.charAt(i);
            if(arr[c - 'a'] != 1){
                found = false;
                break;
            }else continue;
        }
        return found;
    }

This algorithm has a O(n3) complexity, which but naturally isn't great. Can someone suggest a better algorithm.

3 Answers
Related