I'm posting my Java code for the Minimum Window Substring. If you have time and would like to review, please do so, I appreciate that.
Problem
Given a string
string
and a stringtarget
, find the minimum window instring
which will contain all the characters intarget
in complexity O(n).Example:
Input:
string
= "ADOBECODEBANC",target
= "ABC" Output: "BANC" Note:If there is no such window in
string
that covers all characters intarget
, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window instring
.
Java
import java.util.*;
import javafx.util.*;
class Solution {
public String minWindow(String string, String target) {
if (string == null || target == null || string.length() == 0 || target.length() == 0 || string.length() < target.length()) {
return "";
}
int minLeft = 0, minRight = 0, min = string.length();
boolean flag = false;
int targetLength = target.length();
Map<Character, Integer> map = new HashMap<>(targetLength);
for (char character : target.toCharArray()) {
map.put(character, -~map.getOrDefault(character, 0));
}
int left = 0, right = 0;
while (right < string.length()) {
char character = string.charAt(right);
map.put(character, map.getOrDefault(character, 0) - 1);
if (map.get(character) > -1) {
targetLength--;
}
while (targetLength == 0 && left <= right) {
flag = true;
int curLength = -~right - left;
if (curLength <= min) {
minLeft = left;
minRight = right;
min = curLength;
}
char leftChar = string.charAt(left);
map.put(leftChar, -~map.getOrDefault(leftChar, 0));
if (map.get(leftChar) > 0) {
targetLength++;
}
left++;
}
right++;
}
return flag == true ? string.substring(minLeft, -~minRight) : "";
}
}