Question

How to find the minimum substring of string s1 that includes every character of string s2 in Java

Answer 1

import java.util.HashMap;

public class MinSubstring {
    
    public static String minSubstring(String s1, String s2) {
        if (s2.isEmpty() || s1.isEmpty()) return "";
        
        // Frequency map for characters in s2
        HashMap<Character, Integer> charCount = new HashMap<>();
        for (char ch : s2.toCharArray()) {
            charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
        }
        
        int required = charCount.size(); // Number of unique characters in s2
        int left = 0, right = 0, formed = 0;
        HashMap<Character, Integer> substringCount = new HashMap<>();
        int minLen = Integer.MAX_VALUE, start = 0;
        
        while (right < s1.length()) {
            char ch = s1.charAt(right);
            substringCount.put(ch, substringCount.getOrDefault(ch, 0) + 1);
            
            if (charCount.containsKey(ch) && substringCount.get(ch).intValue() == charCount.get(ch).intValue()) {
                formed++;
            }
            
            while (left <= right && formed == required) {
                char temp = s1.charAt(left);
                
                // Update the minimum substring
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                
                substringCount.put(temp, substringCount.get(temp) - 1);
                if (charCount.containsKey(temp) && substringCount.get(temp) < charCount.get(temp)) {
                    formed--;
                }
                left++;
            }
            right++;
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s1.substring(start, start + minLen);
    }
    
    public static void main(String[] args) {
        String s1 = "ADOZBECYDEBAXC";
        String s2 = "ABC";
        
        String result = minSubstring(s1, s2);
        if (!result.isEmpty()) {
            System.out.println("Minimum substring: " + result);
        } else {
            System.out.println("No valid substring found.");
        }
    }
}



/*
run:

Minimum substring: BAXC

*/

 

70+ SQL courses for beginners and professionals