Minimum Window Substring
Problem Description
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Explanation
We are given two strings s and t . We have to find the shortest substring of s which contains all the characters of t.
If there is no such substring of s , we return an empty string "".
What is a Substring ?
A substring is a contiguous sequence of characters within a string. For a string s = "abcdef", a substring must consist of characters that appear consecutively in the original string.
Single-character substrings:
"a", "b", "c", "d", "e", "f"
Two-character substrings:
"ab", "bc", "cd", "de", "ef"
Three-character substrings:
"abc", "bcd", "cde", "def"
Four-character substrings:
"abcd", "bcde", "cdef"
Five-character substrings:
"abcde", "bcdef"
Six-character substring (the whole string itself):
"abcdef"
Invalid Substrings (Non-contiguous sequences):
"acd", "ace", "bac", etc., are not substrings because they skip over characters or mix up the order of characters in s.
Examples
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Constraints:
- m == s.length
- n == t.length
- 1 <= m, n <= 10^5
- s and t consist of uppercase and lowercase English letters.
We will be analysing the solution with the brute force approach and using two pointers/sliding window algorithm. Each approach has its own benefits and challenges regarding how fast it works and how much memory it uses.
Brute Force Approach
Intuition
The first thing that comes to our mind is to generate all substrings of s and then check if that particular substring contains all characters of t in it or not.
If it contains, we will measure its length and store the substring. If not, we will move forward with generating the rest of the substrings.
How to generate all Substrings of a String ?
To generate all substrings of s, we will be using two loops.
We will start from the first character and move through each character of the string one by one. For each character, this is considered as the starting point of the substring.
For each starting character, we iterate over the next character and will continue till the end of the string. We will consider every possible ending point for the substring, ensuring that the ending index is always greater than the starting point (so you get non-empty substrings).
For each pair of start and end points, a substring is formed by selecting characters between the start index and one less than the end index. This way, we will be building all possible substrings.
For example if s = “abcde”,
The start point = 0
The end point = 1
The highlighted part is the substring formed in “abcde”.
Then the end point increments to the next index i.e end point = 2
The highlighted part is the substring formed in “abcde”. Similarly, we will move the end point till the end of the substring.
Once the end point reaches the end of the substring. We will increment the start point and start the same procedure all again until our start point is equal to the length of the substring.
When the start point =1
The end point = 2 The highlighted part is the substring formed , “abcde”
The next substring formed is the highlighted part in “abcde”.
Once, we generate a substring of s, we can check if the substring contains all the characters of t or not .
To check the occurrences of each character in that substring, which data structure can we use ?
Yes, we can maintain a Hash-Table of size 52, to determine the occurrences of each character.
Why Hash-Table of size 52?
Because, we have a total of 52 valid ASCII characters including Lowercase, Uppercase Characters.
How to use a Hash-Table?
It’s simple, we can create an array of size 52.
The character 'a' has the ASCII code 97.
The character 'A' has the ASCII code 65.
If the string s= “aaBcD”, then
'a' has an ASCII value of 97, so the frequency of 'a' will be stored at index 97.
'B' has an ASCII value of 66, so the frequency of 'B' will be stored at index 66.
'c' has an ASCII value of 99, and 'D' has an ASCII value of 68.
How to Insert,Update and Access values from a Hash-Table ?
c-> current character
Map a-z to indices 0-25 using c - 'a' .
Map A-Z to indices 26-51 using c - 'A' + 26.
To access the value present in that index.
- Java-> freqTable[s.charAt(i) >= 'a' ? s.charAt(i) - 'a' : s.charAt(i) - 'A' + 26]++;
- C++->freqTable[s[i] >= 'a' ? s[i] - 'a' : s[i] - 'A' + 26]++;
- Python-> freqTable[ord(s[i]) - ord('a') if 'a' <= s[i] <= 'z' else ord(s[i]) - ord('A') + 26] += 1
- JavaScript-> freqTable[s[i] >= 'a' ? s.charCodeAt(i) - 'a'.charCodeAt(0) : s.charCodeAt(i) - 'A'.charCodeAt(0) + 26]++;
For a-z, the index is calculated as c - 'a' or equivalent.
For A-Z, the index is adjusted with +26 to avoid overlapping with a-z.
Is , there any alternative to a Hash-Table?
Can we think of a data structure that records the character and it's frequency together??
The data structure that aligns with our requirements is a HashMap.
What is a HashMap/Map ?
A data structure that stores key-value pairs in it.
If any duplicate Key enters the map, it just updates the value of that particular key to the newly entered value.
We can perform Insert, Read, Update and Delete operations in a HashMap.
Why is using a Hash-table better than using a Hash-Map ??
Performance !!
Accessing and updating an element in the hash-table has a constant time complexity, O(1).
In contrast, a HashMap can have an average case time complexity of O(1) but can degrade to
O(n) in worst-case scenarios due to collisions or rehashing.
This is particularly important in time-sensitive applications.
Let's use a Hash-Table to store the frequencies of each character of the substring.
Approach
Initialize Variables:Set a variable to represent the minimum length of the substring found so far, initialized to a very large value (infinity).Set a variable to store the smallest valid substring, initialized to an empty string.
Generate All Possible Substrings:Loop through each starting position of the substring in the main string:For each starting position, loop through each possible ending position to generate all substrings starting from that position.
Check Each Substring:For each generated substring:Create a count of the characters required, based on the characters in the target string.Create a count of the characters found in the current substring.Compare the character counts between the current substring and the required characters:If the substring contains all characters with the required frequency, it is a valid substring.
Update Minimum Window:If the current substring is valid and has a length shorter than the previously found minimum length:Update the minimum length and store this substring as the current minimum window substring.
Return Result:If a valid minimum window substring was found, return it.If no valid substring was found, return an empty string.
Dry-Run
String s= "cdbabebca"
String t= "abc"
Answer= "bca" is the shortest substring of s with all characters of t.
General Setup:
- String s: "cdbabebca"
- String t: "abc"
- Objective: Find the shortest substring of s that contains all characters of t.
Step-by-Step Dry Run for i = 0
- Start at the beginning of s (with i = 0).
- Look at substrings starting from index 0 and extending to the right:
- First substring (from 0 to 1): "c"
- Does it contain all characters of "abc"? No.
- Second substring (from 0 to 2): "cd"
- Does it contain all characters of "abc"? No.
- Third substring (from 0 to 3): "cdb"
- Does it contain all characters of "abc"? No.
- Fourth substring (from 0 to 4): "cdba"
- Does it contain all characters of "abc"? Yes.
- Update the minimum window: Current substring "cdba" (length 4).
- Fifth substring (from 0 to 5): "cdbae"
- Does it contain all characters of "abc"? Yes.
- But it’s longer than the current minimum, so we keep "cdba".
- Sixth substring (from 0 to 6): "cdbaeb"
- Does it contain all characters of "abc"? Yes.
- Still longer than the current minimum, so keep "cdba".
- Continue with larger substrings: They will all be longer than "cdba" and already contain all characters of "abc", so no need to update.
Step-by-Step Dry Run for i = 6
- Move to i = 6 (start from index 6 of s).
- Look at substrings starting from index 6:
- First substring (from 6 to 7): "b"
- Does it contain all characters of "abc"? No.
- Second substring (from 6 to 8): "bc"
- Does it contain all characters of "abc"? No.
- Third substring (from 6 to 9): "bca"
- Does it contain all characters of "abc"? Yes.
- Update the minimum window: Current substring "bca" (length 3).
- After processing the substring starting from i = 6, the new minimum window is "bca" (length 3).
Final Result The shortest substring that contains all characters of t = "abc" in s = "cdbabebca" is "bca", and its length is 3.
Summary
- For i = 0, the shortest substring found was "cdba", but we found a shorter one starting from i = 6, which was "bca".
- The overall result is "bca", which is the shortest substring that contains all the characters of "abc".
Brute Force in all Languages.
1. C++ Try on Compiler
class Solution {
public:
string minWindow(string s, string t) {
// Initialize minLength to the maximum possible value
int minLength = INT_MAX;
// Initialize minWindow to store the result
string minWindow = "";
// Traverse all possible substrings of s
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
// Get the current substring from s
string substring = s.substr(i, j - i);
// Check if this substring contains all characters of t
if (containsAllCharacters(substring, t)) {
// If the current substring is smaller than the previous minimum, update minWindow
if (substring.length() < minLength) {
minLength = substring.length();
minWindow = substring;
}
}
}
}
return minWindow; // Return the minimum window substring found
}
bool containsAllCharacters(const string &s, const string &t) {
// Create an array to count frequency of characters in t
int targetCount[52] = {0};
for (char c : t) {
if (isupper(c)) {
targetCount[c - 'A']++; // Map uppercase letters to 0-25
} else if (islower(c)) {
targetCount[c - 'a' + 26]++; // Map lowercase letters to 26-51
}
}
// Create an array to count frequency of characters in the current substring s
int windowCount[52] = {0};
for (char c : s) {
if (isupper(c)) {
windowCount[c - 'A']++; // Map uppercase letters to 0-25
} else if (islower(c)) {
windowCount[c - 'a' + 26]++; // Map lowercase letters to 26-51
}
}
// Check if the current substring contains all characters of t with the required frequency
for (int i = 0; i < 52; i++) {
if (windowCount[i] < targetCount[i]) {
return false; // If any character in s is less than in t, return false
}
}
return true; // Return true if all characters are present in the required frequency
}
};2. Java Try on Compiler
class Solution {
public String minWindow(String s, String t) {
// Initialize minLength to the maximum possible value
int minLength = Integer.MAX_VALUE;
// Initialize minWindow to store the result
String minWindow = "";
// Traverse all possible substrings of s
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
// Get the current substring from s
String substring = s.substring(i, j);
// Check if the substring contains all characters of t
if (containsAllCharacters(substring, t)) {
// If the current substring is smaller than the previous minimum, update minWindow
if (substring.length() < minLength) {
minLength = substring.length();
minWindow = substring;
}
}
}
}
// Return the minimum window substring
return minWindow;
}
// Method to check if the substring contains all characters of t
private static boolean containsAllCharacters(String s, String t) {
// Create an array to count the frequency of characters in t
int[] targetCount = new int[52];
for (char c : t.toCharArray()) {
targetCount[charToIndex(c)]++;
}
// Create an array to count the frequency of characters in the current substring s
int[] windowCount = new int[52];
for (char c : s.toCharArray()) {
windowCount[charToIndex(c)]++;
}
// Check if the current substring contains all characters of t with the required frequency
for (int i = 0; i < 52; i++) {
if (windowCount[i] < targetCount[i]) {
return false; // If the current substring does not have enough of any character, return false
}
}
// If the substring contains all characters, return true
return true;
}
// Method to map characters to indices (0-51)
private static int charToIndex(char c) {
if (Character.isUpperCase(c)) {
return c - 'A'; // Uppercase letters map to 0-25
} else {
return c - 'a' + 26; // Lowercase letters map to 26-51
}
}
}3. Python Try on Compiler
class Solution:
def minWindow(self, s: str, t: str) -> str:
# Helper function to map characters to indices (0-51)
def char_to_index(c):
if 'A' <= c <= 'Z': # Uppercase letters
return ord(c) - ord('A')
elif 'a' <= c <= 'z': # Lowercase letters
return ord(c) - ord('a') + 26
else:
raise ValueError("Input string contains unsupported characters")
# Helper function to check if a window contains all characters of t
def contains_all_characters(window_count, target_count):
for i in range(52):
if window_count[i] < target_count[i]: # If any character count is insufficient
return False
return True
# Edge case: If s or t is empty
if not s or not t:
return ""
# Initialize the target character counts
target_count = [0] * 52
for c in t:
target_count[char_to_index(c)] += 1
# Initialize the window counts
window_count = [0] * 52
# Sliding window pointers and result variables
left, right = 0, 0
min_length = float('inf')
min_window = ""
while right < len(s):
# Add the current character to the window
window_count[char_to_index(s[right])] += 1
# Try to shrink the window while it contains all characters of t
while contains_all_characters(window_count, target_count):
current_length = right - left + 1
if current_length < min_length: # Update the result if a smaller window is found
min_length = current_length
min_window = s[left:right + 1]
# Shrink the window by removing the left character
window_count[char_to_index(s[left])] -= 1
left += 1
# Expand the window by moving the right pointer
right += 1
return min_window4. JavaScript Try on Compiler
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
// Initialize minLength to the maximum possible value
let minLength = Infinity;
// Initialize minWindow to store the result
let minWindow = "";
// Traverse all possible substrings of s
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
// Get the current substring from s
let substring = s.substring(i, j);
// Check if the substring contains all characters of t
if (containsAllCharacters(substring, t)) {
// If the current substring is smaller than the previous minimum, update minWindow
if (substring.length < minLength) {
minLength = substring.length;
minWindow = substring;
}
}
}
}
// Return the minimum window substring
return minWindow;
};
// Helper function to check if the substring contains all characters of t
function containsAllCharacters(s, t) {
// Create an array to count the frequency of characters in t
let targetCount = Array(52).fill(0);
for (let c of t) {
targetCount[charToIndex(c)]++;
}
// Create an array to count the frequency of characters in the current substring s
let windowCount = Array(52).fill(0);
for (let c of s) {
windowCount[charToIndex(c)]++;
}
// Check if the current substring contains all characters of t with the required frequency
for (let i = 0; i < 52; i++) {
if (windowCount[i] < targetCount[i]) {
return false; // If the current substring does not have enough of any character, return false
}
}
// If the substring contains all characters, return true
return true;
}
// Helper function to map characters to indices (0-51)
function charToIndex(c) {
if (c >= 'A' && c <= 'Z') {
return c.charCodeAt(0) - 'A'.charCodeAt(0); // Uppercase letters map to 0-25
} else {
return c.charCodeAt(0) - 'a'.charCodeAt(0) + 26; // Lowercase letters map to 26-51
}
}
Time Complexity: O(n^2 ⋅ (m+n))
- Outer loop (i loop): Runs O(n), where n is the length of s.
- Inner loop (j loop): For each i, it runs up to O(n), making the total iterations O(n^2).
- Substring creation: Each substring takes O(n) space and time to create.
- containsAllCharacters: Takes O(m+k), where m is the length of t and k is the length of the current substring.
Overall time complexity: O(n^2⋅(m+n)).
Space Complexity: O(n)
- Auxiliary space Complexity:
The auxiliary space complexity is constant, O(1), because we only use two arrays (targetCount and windowCount), each of size 52 to store the frequency counts of characters. The size of these arrays does not depend on the size of the input strings s and t, making the space usage constant. - Total space Complexity:
The total space complexity considers the space used to store the input strings, as well as the substrings generated. The function does not create any new data structures that scale with the input size, except for the space used by the sliding window substring, which can be as large as n in the worst case. Therefore, the overall space complexity is O(n), wherenis the length of string s.
Overall space complexity: O(n).
Looking at the constraints where the size of string is 10^5 results in Time Limit Exceeded since, the substring takes O(n^3) time in the worst case which is inefficient. The interviewer will be unhappy with the solution. Let's figure out a better solution.
Optimized Approach
Intuition
When trying to find the minimum substring in s that contains all characters of t, a straightforward approach would be to consider all possible substrings of s and check each one to see if it contains all the characters of t.
For example, with s = "aabcde" and t = "abc":
- We’d start by looking at the substring "a", but it doesn’t contain all characters of t.
- Then we’d try "aa", "aab", "aabc", and so on, checking each time if the substring has all characters of t.
- If a substring has all characters of t, we could record its length and continue to see if there’s a shorter one that also meets the requirement.
However, this approach is highly inefficient, especially with longer strings, because:
- We end up generating and checking too many substrings.
- We may repeatedly check the same characters in different overlapping substrings.
Notice that as we generate each substring, we’re often re-checking characters that we’ve already checked. For example, if we already checked the substring "aab", we don’t need to fully re-check the characters "aa" when moving to "aabc" , we’re only adding the new character "c".
This observation suggests that instead of generating new substrings from scratch, we could maintain a dynamic range of characters (or a "window") that expands and shrinks to cover the necessary characters.
To avoid redundant checks, we can think of a sliding window that "slides" across s. Here’s how this window would work:
- Expand the window to the right until it contains all characters of t.
- Once we have all characters, shrink the window from the left to try to make it as small as possible while still containing all characters of t.
- Repeat this process until we’ve found the smallest valid window.
- By adjusting the window in this way, we avoid generating substrings from scratch and keep track of characters only once as they enter and leave the window.
How to check if all the characters of t are in s ?
We can tally the characters of t with s.
We will declare Hash-Table (frequency array) of size 52 to store the frequency of each character of t and then tally it with the substrings we encounter.
How are we tallying ?
Suppose s="abdefc" and t="ad"
We will push the frequencies of all characters of t into a frequency array, the frequencies will be
a->1
d->1
The first substring is "a", update the frequency table i.e reduce frequency of a by 1
a->0
b->1
The second substring is "ab" , no update required.
The third substring is "abd", update the frequency table i.e reduce the frequency of b by 1
a->0
b->0
Our , tally operation concludes that the substring "abd" has all characters of t.
Approach
Initialize Character Counts for t:
- First, create a frequency map of characters in t. This map will help us track how many occurrences of each character we need in the window.
Expand the Window (right pointer):
- Start with two pointers, left and right, both at the beginning of s.
Move right to expand the window and include more characters. - For each character s[right], if it’s a required character in t, decrease its frequency in the map.
- If its frequency becomes zero or below, it means we have enough of that character in the window.
Check for a Valid Window:
- Whenever our window contains all characters of t (tracked using a count variable that tallies required characters), we check if it’s the smallest window found so far.
- Update the minimum length and starting index if this window is smaller.
Shrink the Window (left pointer):
- To potentially find a smaller valid window, increment left to shrink the window.
- As left moves forward, if a character leaves the window, update its frequency in the map.
- If it’s a required character that’s now missing from the window, decrease count.
Result:
After the loop, the minimum-length window recorded is the smallest substring that contains all characters of t.
Let's Visualize it with a Video
Dry-Run
String s= "cdbabebca"
String t= "abc"
Answer= "bca" is the shortest substring of s with all characters of t.
Input Details
- s = "cdbabebca"
- t = "abc"
Variables:
- n = 9, m = 3
- freq for t (frequency of required characters):
- 'a' → freq[26] = 1
- 'b' → freq[1] = 1
- 'c' → freq[2] = 1
- Sliding window variables:
- left = 0, right = 0, count = 0
- minLen = INT_MAX, startIndex = 0
- windowFreq is initialized with all zeros.
Dry Run IterationsStep 1: right = 0, character = 'c'
- Update windowFreq[2]: windowFreq[2] = 1.
- 'c' is required, so count = 1.
- No valid window (count < m).
Window: s[0:0] → "c"
Pointers: left = 0, right = 0
Step 2: right = 1, character = 'd'
- 'd' is not in t. windowFreq unchanged for required characters.
- No change in count.
Window: s[0:1] → "cd"
Pointers: left = 0, right = 1
Step 3: right = 2, character = 'b'
- Update windowFreq[1]: windowFreq[1] = 1.
- 'b' is required, so count = 2.
- No valid window (count < m).
Window: s[0:2] → "cdb"
Pointers: left = 0, right = 2
Step 4: right = 3, character = 'a'
- Update windowFreq[26]: windowFreq[26] = 1.
- 'a' is required, so count = 3.
- A valid window is found: "cdba".
- Update minLen = 4 and startIndex = 0.
Window: s[0:3] → "cdba"
Pointers: left = 0, right = 3
Step 5: Shrink the window by moving left
- Remove 'c': windowFreq[2] = 0.
- 'c' is now less than required, so count = 2.
- No valid window (count < m).
Window: s[1:3] → "dba"
Pointers: left = 1, right = 3
Step 6: right = 4, character = 'b'
- Update windowFreq[1]: windowFreq[1] = 2.
- No change in count (still 2 because 'b' is already fully matched).
Window: s[1:4] → "dbab"
Pointers: left = 1, right = 4
Step 7: right = 5, character = 'e'
- 'e' is not in t. No change in count.
Window: s[1:5] → "dbabe"
Pointers: left = 1, right = 5
Step 8: right = 6, character = 'b'
- Update windowFreq[1]: windowFreq[1] = 3.
- No change in count.
Window: s[1:6] → "dbabeb"
Pointers: left = 1, right = 6
Step 9: right = 7, character = 'c'
- Update windowFreq[2]: windowFreq[2] = 1.
- 'c' is required, so count = 3.
- A valid window is found: "dbabebc".
- No update to minLen since it’s larger than the current smallest.
Window: s[1:7] → "dbabebc"
Pointers: left = 1, right = 7
Step 10: Shrink the window by moving left
- Remove 'd': windowFreq[3] unchanged for required characters.
- Move left = 2.
Window: s[2:7] → "babebc"
Pointers: left = 2, right = 7
- Remove 'b': windowFreq[1] = 2.
- Still valid window: "abebc".
- Move left = 3.
Window: s[3:7] → "abebc"
Pointers: left = 3, right = 7
- Remove 'a': windowFreq[26] = 0, count = 2.
- No valid window now.
Step 11: right = 8, character = 'a'
- Update windowFreq[26]: windowFreq[26] = 1.
- 'a' is required, so count = 3.
- A valid window is found: "bebca".
Step 12: Shrink the window by moving left
- update windowFreq[27]: windowFreq[27] =1.
- still a valid window
Window: s[5:8] → "ebca"
Pointers: left = 5, right = 8
Since, it is still valid!
Step 13: Shrink the window by moving left
- update windowFreq[30]: windowFreq[30]=0
Window: s[6:8] → "bca"
Pointers: left = 6, right = 8
Final Result
The smallest valid window is "bca" with length 3.
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
string minWindow(string s, string t) {
// Initialize variables
int n = s.length(), m = t.length();
vector<int> freq(52, 0); // Frequency array of size 52
// Helper lambda to map characters to indices
auto charToIndex = [](char c) {
return isupper(c) ? c - 'A' : c - 'a' + 26;
};
// Step 1: Count frequency of characters in t
for (char ch : t) {
freq[charToIndex(ch)]++;
}
// Define pointers, count, minimum length, and starting index
int left = 0, right = 0, count = 0;
int minLen = INT_MAX, startIndex = 0;
// Sliding window to expand and contract as needed
vector<int> windowFreq(52, 0); // Frequency array for the current window
while (right < n) {
// Expand window by including s[right]
char curr = s[right];
int currIndex = charToIndex(curr);
windowFreq[currIndex]++;
// Increment count if this character is required and still valid
if (windowFreq[currIndex] <= freq[currIndex]) {
count++;
}
// Check for a valid window and try to shrink it
while (count == m) {
// Update minimum length window if needed
if (right - left + 1 < minLen) {
minLen = right - left + 1;
startIndex = left;
}
// Shrink window by moving left pointer
char leftChar = s[left];
int leftIndex = charToIndex(leftChar);
windowFreq[leftIndex]--;
if (windowFreq[leftIndex] < freq[leftIndex]) {
count--;
}
left++;
}
right++;
}
// Return result based on minimum length found
return minLen == INT_MAX ? "" : s.substr(startIndex, minLen);
}
};2. Java Try on Compiler
class Solution {
// Helper method to map characters to indices
private int charToIndex(char c) {
return Character.isUpperCase(c) ? c - 'A' : c - 'a' + 26;
}
public String minWindow(String s, String t) {
// Initialize variables
int n = s.length();
int m = t.length();
int[] freq = new int[52];
// Step 1: Count frequency of characters in t
for (char ch : t.toCharArray()) {
freq[charToIndex(ch)]++;
}
// Define pointers, count, minimum length, and starting index
int left = 0, right = 0, count = 0;
int minLen = Integer.MAX_VALUE, startIndex = 0;
// Frequency array for the current window
int[] windowFreq = new int[52];
// Sliding window to expand and contract as needed
while (right < n) {
// Expand window by including s[right]
char curr = s.charAt(right);
int currIdx = charToIndex(curr);
windowFreq[currIdx]++;
// Increment count if the current character is valid for t
if (windowFreq[currIdx] <= freq[currIdx]) {
count++;
}
// Check for a valid window and try to shrink it
while (count == m) {
// Update minimum length window if needed
if (right - left + 1 < minLen) {
minLen = right - left + 1;
startIndex = left;
}
// Shrink window by moving left pointer
char leftChar = s.charAt(left);
int leftIdx = charToIndex(leftChar);
windowFreq[leftIdx]--;
if (windowFreq[leftIdx] < freq[leftIdx]) {
count--;
}
left++;
}
right++;
}
// Return result based on minimum length found
return minLen == Integer.MAX_VALUE ? "" : s.substring(startIndex, startIndex + minLen);
}
}
3. Python Try on Compiler
class Solution:
def minWindow(self, s: str, t: str) -> str:
# Helper function to map character to index in the frequency array
def char_to_index(c):
return ord(c) - ord('A') if c.isupper() else ord(c) - ord('a') + 26
# Initialize frequency count for characters in t
freq = [0] * 52
for char in t:
freq[char_to_index(char)] += 1
# Initialize pointers, counts, and result parameters
left, right = 0, 0
count = 0
min_len = float('inf')
start_index = 0
n, m = len(s), len(t)
# Frequency array for the current window
window_freq = [0] * 52
# Sliding window
while right < n:
# Expand window by including s[right]
curr_idx = char_to_index(s[right])
window_freq[curr_idx] += 1
# Increment count if the current character is valid for t
if window_freq[curr_idx] <= freq[curr_idx]:
count += 1
# Shrink window if valid
while count == m:
# Update minimum length window if needed
if right - left + 1 < min_len:
min_len = right - left + 1
start_index = left
# Shrink the window by moving left
left_idx = char_to_index(s[left])
window_freq[left_idx] -= 1
if window_freq[left_idx] < freq[left_idx]:
count -= 1
left += 1
right += 1
# Return result based on minimum length found
return "" if min_len == float('inf') else s[start_index:start_index + min_len]
4. JavaScript Try on Compiler
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
// Helper function to map characters to indices in the frequency array
const charToIndex = (c) => {
return c >= 'A' && c <= 'Z' ? c.charCodeAt(0) - 'A'.charCodeAt(0)
: c.charCodeAt(0) - 'a'.charCodeAt(0) + 26;
};
// Initialize frequency array for characters in t
const freq = new Array(52).fill(0);
// Fill frequency array with characters in t
for (let char of t) {
freq[charToIndex(char)]++;
}
// Initialize pointers, counts, and result parameters
let left = 0, right = 0, count = 0;
let minLen = Infinity, startIndex = 0;
const n = s.length, m = t.length;
// Frequency array for the current window
const windowFreq = new Array(52).fill(0);
// Sliding window approach
while (right < n) {
// Expand window by including s[right]
let currIdx = charToIndex(s[right]);
windowFreq[currIdx]++;
// Increment count if the current character is part of t
if (windowFreq[currIdx] <= freq[currIdx]) {
count++;
}
right++; // Move right pointer
// When all characters in t are matched, try to shrink window
while (count === m) {
// Update minimum length window if this window is smaller
if (right - left < minLen) {
minLen = right - left;
startIndex = left;
}
// Shrink the window from the left
let leftIdx = charToIndex(s[left]);
windowFreq[leftIdx]--;
// If left character is part of t, reduce count
if (windowFreq[leftIdx] < freq[leftIdx]) {
count--;
}
left++; // Move left pointer to shrink window
}
}
// Return the result based on the minimum length found
return minLen === Infinity ? "" : s.slice(startIndex, startIndex + minLen);
};
Time Complexity: O(m+n)
Frequency Count of Characters in t:
- In the initial step, we iterate through t to count the frequency of each character.
- This takes O(m) time, where m is the length of t.
Sliding Window with Two Pointers (left and right):
- The main part of the algorithm is the sliding window, where right expands the window by moving to the right through s, and the left contracts the window as needed to minimize it.
- Both pointers left and right traverse s only once, so this part of the algorithm takes O(n) time, where n is the length of s.
- Although there is a nested while loop (where left is moved forward), the overall movement of left and right combined is at most n steps each, making this entire part O(n).
Overall Time Complexity:
- The overall time complexity is O(m+n), where m is the length of t and n is the length of s.
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm that is not part of the input.
An array of size 52 is used to store the frequency of each character,so it has constant space i.e. O(1).
Other variables used in the algorithm are a fixed number of integers and do not grow with input size.
Thus, the auxiliary space complexity is: O(1), as the space used is constant and does not depend on the size of the input.
Total Space Complexity
The input string s is stored in memory, which takes O(n) space.
The auxiliary space from the character frequency array is O(1).
Thus, the total space complexity is: O(n), due to the input string.
Learning Tip
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.