Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Problem Challenge 3: Smallest Window containing Substring
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string and a pattern, find the smallest substring in the given string which has all the character occurrences of the given pattern.

Example 1:

Input: String="aabdec", Pattern="abc"  
Output: "abdec"  
Explanation: The smallest substring having all characters of the pattern is "abdec"

Example 2:

Input: String="aabdec", Pattern="abac"  
Output: "aabdec"  
Explanation: The smallest substring having all characters occurrences of the pattern is "aabdec"

Example 3:

Input: String="abdbca", Pattern="abc"  
Output: "bca"  
Explanation: The smallest substring having all characters of the pattern is "bca".

Example 4:

Input: String="adcad", Pattern="abc"  
Output: ""  
Explanation: No substring in the given string has all characters of the pattern

Constraints:

  • m == String.length
  • n == Pattern.length
  • 1 <= m, n <= 10<sup>5</sup>
  • String and Pattern consist of uppercase and lowercase English letters.

Solution

To solve this problem, we use the sliding window technique. This approach helps us dynamically adjust the range of the substring we're considering. We start with two pointers, one at the beginning and another that expands to include new characters. As we move the right pointer to include characters, we check if the current window contains all the characters from pattern in the required frequency. Once it does, we try to shrink the window from the left to find the smallest possible window. This method is efficient because it avoids redundant calculations by reusing information from the previous state.

This approach is effective because it ensures that each character in s is processed at most twice (once by each pointer), resulting in a linear time complexity relative to the length of s. The space complexity is manageable, as we only store the frequency of characters in a hash map. This guarantees that the solution is both time and space efficient.

Step-by-step Algorithm

  1. Initialize Variables:

    • Create a hash map to store the frequency of characters in pattern.
    • Initialize variables: windowStart to track the start of the window, minLength to track the minimum window size, matched to count matched characters, and subStrStart to remember the start index of the smallest window.

  2. Expand the Window:

    • Iterate through s with windowEnd.
    • For each character at windowEnd, check if it is in the hash map. If yes, decrement its frequency in the map.
    • If the character's frequency in the map is zero or more, increment the matched count.

  3. Shrink the Window:

    • While matched equals the length of pattern, it means the current window contains all characters of pattern.
    • Update the minLength and subStrStart if the current window size is smaller than the previous smallest window.
    • Move the windowStart to the right to shrink the window. If the character at windowStart is in the hash map, increase its frequency in the map. If its frequency becomes zero, decrement the matched count.

  4. Return Result:

    • After processing all characters, if minLength is greater than the length of s, return an empty string. Otherwise, return the substring starting at subStrStart with the length of minLength.

Algorithm Walkthrough

Example:

  • s = "aabdec"
  • t = "abc"

  1. Initialize:

    • charFrequencyMap: {a: 1, b: 1, c: 1}
    • windowStart = 0, matched = 0, minLength = 7, subStrStart = 0

  2. Iteration:

    • windowEnd = 0: rightChar = 'a'
      • charFrequencyMap: {a: 0, b: 1, c: 1}, matched = 1
    • windowEnd = 1: rightChar = 'a'
      • charFrequencyMap: {a: -1, b: 1, c: 1}, matched = 1
    • windowEnd = 2: rightChar = 'b'
      • charFrequencyMap: {a: -1, b: 0, c: 1}, matched = 2
    • windowEnd = 3: rightChar = 'd'
      • No change in charFrequencyMap or matched
    • windowEnd = 4: rightChar = 'e'
      • No change in charFrequencyMap or matched
    • windowEnd = 5: rightChar = 'c'
      • charFrequencyMap: {a: -1, b: 0, c: 0}, matched = 3
      • matched == t.length(): Update minLength = 6, subStrStart = 0
      • windowStart = 1: leftChar = 'a'
        • charFrequencyMap: {a: 0, b: 0, c: 0}, matched = 3, minLength = 5, subStrStart = 1
      • windowStart = 2: leftChar = 'a'
        • charFrequencyMap: {a: 1, b: 0, c: 0}, matched = 2

  3. Result:

    • minLength = 5, subStrStart = 1
    • Return s.substring(1, 1 + 5) => "abdec"
Image

Code

Here is what our algorithm will look:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Creating the frequency map: The algorithm first creates a frequency map of the characters in the pattern. This step takes O(M) time, where M is the length of the pattern.

  • Sliding window traversal: The algorithm uses a sliding window approach to traverse through the string. The outer loop runs for each character in the string, so the loop runs O(N) times, where N$ is the length of the input string.

  • Character frequency updates: For each character in the window, the algorithm performs constant-time operations such as updating the frequency in the charFrequencyMap and adjusting the matched count. These operations take O(1) time on average, as hash map operations like put() and get() are constant on average.

Overall time complexity: The total time complexity is O(N + M), where N$ is the length of the string and M$ is the length of the pattern.

Space Complexity

  • HashMap space: The algorithm uses a hash map, charFrequencyMap, to store the frequency of characters in the pattern. This requires O(M) space, where M$ is the number of unique characters in the pattern.

  • Additional variables: The algorithm uses a few extra variables such as windowStart, windowEnd, matched, minLength, and subStrStart, all of which require constant space, O(1).

Overall space complexity: O(M), where M$ is the number of unique characters in the pattern.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible