Problem:
Given a Source string and a Target string, find the shortest substring in Source string that contains all unique characters in target string.For Example:
Given source string "YMNZZDXQFHYAZX" and target string "XYZ"
The shortest substring in "YMNZZDXQFHYAZX" that contains "XYZ" is "YAZX"
Note:
If no solution, return the empty string "".
We can assume there is only one unique answer window in source string.
Solution:
The problem is fit for sliding window. We use two pointers to mark a focus window's left and right edge. We slide the right pointer to add more characters to the window for consideration, we move the left pointer to remove characters from the window. For a particular window, we exam the condition to update a result candidate. The remaining design work is now boiling down to when to move right pointer, when to move left pointer.
For this particular problem, we move the right pointer 1 step at a time until the condition "substring in Source string that contains all unique characters in target string" meets. Once the condition is met, we move the left pointer one step at time, until the condition no longer meet, during the process, we can find the shortest substring end at the right pointer's position that satisfy the condition.
After that, we move the right pointer in order to restore the condition, then we move the left pointer in order to break the condition, during the process, we will find another shortest substring candidate.
Then we repeat until the right pointer reach the end of the string.
import java.util.*;
public class Solution {
public static String shortestSubstring(String s, String t) { //YMNZZDXQFHYAZX XYZ
if(s.length() == 0 || t.length() == 0) return "";
HashMap<Character, Integer> counter = new HashMap<>();
int left = 0, right = 0;
int minL = 0, minR = Integer.MAX_VALUE; //10,13
Set<Character> tt = new HashSet<>();
for(Character c : t.toCharArray()) {
tt.add(c);
}
while(right < s.length()) {
char c = s.charAt(right);
if(tt.contains(c)) {
counter.put(c, counter.getOrDefault(c, 0) + 1);
}
while(counter.size() == tt.size()) {
if(right - left < minR - minL) {
minL = left;
minR = right;
}
char tmp = s.charAt(left);
if(tt.contains(tmp)) {
if(counter.get(tmp).equals(1)) {
counter.remove(tmp);
} else {
counter.put(tmp, counter.get(tmp) - 1);
}
}
left++;
}
right++;
}
if(minR == Integer.MAX_VALUE)
return "";
return s.substring(minL, minR+1);
}
public static void main(String...args) {
System.out.println(shortestSubstring("YMNZZDXQFHYAZX", "XYZ"));
}
}
public class Solution {
public static String shortestSubstring(String s, String t) { //YMNZZDXQFHYAZX XYZ
if(s.length() == 0 || t.length() == 0) return "";
HashMap<Character, Integer> counter = new HashMap<>();
int left = 0, right = 0;
int minL = 0, minR = Integer.MAX_VALUE; //10,13
Set<Character> tt = new HashSet<>();
for(Character c : t.toCharArray()) {
tt.add(c);
}
while(right < s.length()) {
char c = s.charAt(right);
if(tt.contains(c)) {
counter.put(c, counter.getOrDefault(c, 0) + 1);
}
while(counter.size() == tt.size()) {
if(right - left < minR - minL) {
minL = left;
minR = right;
}
char tmp = s.charAt(left);
if(tt.contains(tmp)) {
if(counter.get(tmp).equals(1)) {
counter.remove(tmp);
} else {
counter.put(tmp, counter.get(tmp) - 1);
}
}
left++;
}
right++;
}
if(minR == Integer.MAX_VALUE)
return "";
return s.substring(minL, minR+1);
}
public static void main(String...args) {
System.out.println(shortestSubstring("YMNZZDXQFHYAZX", "XYZ"));
}
}
The time complexity is O(S + T), we iterate Source and Target at least once. The space complexity is O(S + T), the HashSet has size O(T) and the HashMap has size O(T) but the final string could have size O(S).
