1. Introduction

In this tutorial, we will learn how to find the shortest substring of a given string that contains all the distinct characters of the string itself. This problem is a common scenario in interviews and competitive programming, and it can be solved efficiently using the sliding window technique along with a HashMap to keep track of character frequencies.

2. Program Steps

1. Define a main method as the entry point of the program.

2. Initialize the input String for which we want to find the shortest all characters substring.

3. Initialize two HashMaps to keep track of the character frequencies in the current window and in the entire string.

4. Iterate over the string to fill the frequency map of the entire string.

5. Use two pointers (left and right) to maintain the current window and find the shortest all characters substring.

6. Iterate the string using the right pointer and update the current window map.

7. If the current window contains all characters, try to minimize the window size by moving the left pointer.

8. Update the minimum length and starting index of the all characters substring whenever a smaller valid window is found.

9. After iterating through the string, print the shortest all characters substring.

3. Code Program

import java.util.HashMap;

public class ShortestAllCharactersSubstring {

    public static void main(String[] args) {

        // Step 2: Initialize the input String
        String str = "abdbca";

        // Step 3: Initialize HashMaps to keep track of character frequencies
        HashMap<Character, Integer> strFreqMap = new HashMap<>();
        HashMap<Character, Integer> windowFreqMap = new HashMap<>();

        // Step 4: Fill the frequency map of the entire string
        for (char c : str.toCharArray()) {
            strFreqMap.put(c, strFreqMap.getOrDefault(c, 0) + 1);
        }

        int left = 0, minLength = Integer.MAX_VALUE, startIndex = 0;

        // Step 5: Use two pointers to maintain the current window
        for (int right = 0; right < str.length(); right++) {
            char rightChar = str.charAt(right);
            windowFreqMap.put(rightChar, windowFreqMap.getOrDefault(rightChar, 0) + 1);

            // Step 7: Minimize the window size by moving the left pointer
            while (windowFreqMap.equals(strFreqMap)) {
                if (right - left < minLength) {
                    minLength = right - left;
                    startIndex = left;
                }

                char leftChar = str.charAt(left++);
                windowFreqMap.put(leftChar, windowFreqMap.get(leftChar) - 1);
                if (windowFreqMap.get(leftChar) == 0) {
                    windowFreqMap.remove(leftChar);
                }
            }
        }

        // Step 9: Print the shortest all characters substring
        System.out.println("Shortest All Characters Substring: " + str.substring(startIndex, startIndex + minLength + 1));
    }
}

Output:

Shortest All Characters Substring: bdbca

4. Step By Step Explanation

– Step 1: The main method is defined, which acts as the starting point of the program.

– Step 2: We initialize the input String str with the value "abdbca".

– Steps 3-4: We initialize two HashMaps to keep track of character frequencies and fill the frequency map of the entire string.

– Step 5: We define two pointers, left and right, to maintain the current window of characters in the string.

– Steps 6-7: We iterate the string using the right pointer, and for each character, we update the current window map and try to minimize the window size by moving the left pointer whenever the current window contains all characters.

– Step 8: We update the minimum length and starting index of the all characters substring whenever we find a smaller valid window.

– Step 9: After iterating through the string, we print the shortest all characters substring found.

This approach ensures that we find the shortest substring containing all characters in the given string efficiently.