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 besolution(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.