LeetCode 76: Minimum Window Substring - Java

Question

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 string target, find the minimum window in string which will contain all the characters in target 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 in target, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in string.

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) : "";
    }
}

Reference

• Question

• Solution

• Discussion

Answer 1

I have some suggestions.

Extract some of the logic to methods.

In your code, I see at least three sections of code that could be in methods. In my opinion, those extraction will help with the reading and make the code a bit shorter.

1. The validation of the parameters.

Before

if (string == null || target == null || string.length() == 0 || target.length() == 0 || string.length() < target.length()) {
   return "";
}

After

public String minWindow(String string, String target) {
   //[...]
   if (haveInvalidParameters(string, target)) {
      return "";
   }
   //[...]
}

private boolean haveInvalidParameters(String string, String target) {
   return string == null || target == null || string.length() == 0 || target.length() == 0 || string.length() < target.length();
}

2. The map initialization.

Before

//[...]
Map<Character, Integer> map = new HashMap<>(targetLength);
for (char character : target.toCharArray()) {
   map.put(character, -~map.getOrDefault(character, 0));
}
//[...]

After

public String minWindow(String string, String target) {
   //[...]
   Map<Character, Integer> map = initializeMap(target, targetLength);
   //[...]
}

private Map<Character, Integer> initializeMap(String target, int targetLength) {
   Map<Character, Integer> map = new HashMap<>(targetLength);
   for (char character : target.toCharArray()) {
      map.put(character, -~map.getOrDefault(character, 0));
   }
   return map;
}

3. The substring section.

Before

public String minWindow(String string, String target) {
   //[...]
   return flag == true ? string.substring(minLeft, -~minRight) : "";
}

After

public String minWindow(String string, String target) {
   //[...]
   return applySubstring(string, minLeft, minRight, flag);
}

private String applySubstring(String string, int minLeft, int minRight, boolean flag) {
   return flag == true ? string.substring(minLeft, -~minRight) : "";
}

Try to keep the variable declarations at the top of the blocks.

Generally in Java, we try to put the variable declarations at the top of the blocks.

• Code Conventions for the Java (Revised April 20, 1999)

Before

int left = 0, right = 0;

After

int minLeft = 0, minRight = 0, min = string.length();
int left = 0, right = 0;

You can simplify the boolean expression

return flag == true ? string.substring(minLeft, -~minRight) : "";

is equals to

return flag ? string.substring(minLeft, -~minRight) : "";