Minimum Substring with all chars

Minimum Substring with all chars

·

2 min read

Problem Statement: You have two strings, s and t. The string t contains only unique elements. Find and return the minimum consecutive substring of s that contains all of the elements from t.

It's guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.

Example: For s = "adobecodebanc" and t = "abc", the output should be
solution(s, t) = "banc".

Solution: We can use two pointer approach to solve this problem, start with the first index, keep increasing the right index until the chars in s covers all the chars in t. Now keep increasing the left index and keep getting the smaller substring that exists.

String solution(String s, String t) {

    if(s.length()==0 || t.length()==0)
    return t;

    int freqs[] = new int[26];
    int freqt[] = new int[26];

    for(int i=0; i<t.length(); i++) {
        freqt[t.charAt(i)-'a']++;
    }

    int minLength = Integer.MAX_VALUE;
    int startIndex = 0;
    int uniqueT = t.length();
    int uniqueS = 0;

    int i=0; int j=0;

    for(j=0; j<s.length(); j++) {

        // keep a track of the unique chars in string s
        char c = s.charAt(j);
        freqs[c - 'a']++;
        if (freqs[c - 'a'] == freqt[c - 'a']) uniqueS++;

        // while the unique chars are same, keep increasing i and getting the smallest substring  
        while (uniqueS == uniqueT) {
            if (j - i + 1 < minLength) {
                minLength = j - i + 1;
                startIndex = i;
            }
            char leftChar = s.charAt(i);
            freqs[leftChar - 'a']--;
            if (freqs[leftChar - 'a'] < freqt[leftChar - 'a']) uniqueS--;
            i++;
        }
    }
    return s.substring(startIndex, startIndex + minLength);

}

Time Complexity : O(n) - where n is the length of the string s.