Smallest window in a String containing all characters of other String
Last Updated : 06 Aug, 2025
Given two strings s and p, the task is to find the smallest substring in s that contains all characters of p, including duplicates. If no such substring exists, return "". If multiple substrings of the same length are found, return the one with the smallest starting index.
Examples:
Input: s = "timetopractice", p = "toc"
Output: toprac
Explanation: "toprac" is the smallest substring in which "toc" can be found.
Input: s = "zoomlazapzo", p = "oza"
Output: apzo
Explanation: "apzo" is the smallest substring in which "oza" can be found.
[Naive Approach] By Generating all the Substrings - O(n^3) time and O(n) space:
The very basic idea to solve this problem is that we can generate all possible substrings of the given string s and checking each substring to see if it contains all characters of string p. This checking can be done by a helper function that counts the frequency of each character in p equals with frequency of the chosen substring. If a substring contains all characters of the p, then its length is compared to the current minimum length and the smallest substring is updated accordingly. The process continues until all substrings have been checked.
C++ #include <climits> #include <iostream> #include <string> using namespace std; bool hasAllChars(string &sub, string &p) { int count[256] = {0}; // Count the frequency of each // character in the pattern for (char ch : p) count[ch]++; // For each character in the substring, // decrement its count for (char ch : sub) { if (count[ch] > 0) count[ch]--; } // If all counts in the count array are zero, // the substring contains all characters of the pattern for (int i = 0; i < 256; i++) { if (count[i] > 0) return false; } return true; } // Function to find the smallest substring // containing all characters of the pattern string minWindow(string &s, string &p) { int n = s.length(); int minLen = INT_MAX; string res = ""; // Generate all substrings // of the given string for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { string sub = s.substr(i, j - i + 1); // Check if the substring contains // all characters of the pattern if (hasAllChars(sub, p)) { int currLen = sub.length(); // Update the result if the current // substring is smaller if (currLen < minLen) { minLen = currLen; res = sub; } } } } return res; } int main() { string s = "timetopractice"; string p = "toc"; string res = minWindow(s, p); if (!res.empty()) cout << res << endl; else cout << "" << endl; return 0; } class GfG { // Function to check if a substring contains // all characters of the pattern static boolean hasAllChars(String sub, String p) { int[] count = new int[256]; // Count the frequency of each // character in the pattern for (int i = 0; i < p.length(); i++) { count[p.charAt(i)]++; } // For each character in the substring, // decrement its count for (int i = 0; i < sub.length(); i++) { if (count[sub.charAt(i)] > 0) count[sub.charAt(i)]--; } // If all counts in the count array are zero, // the substring contains all characters of the pattern for (int i = 0; i < 256; i++) { if (count[i] > 0) return false; } return true; } // Function to find the smallest substring // containing all characters of the pattern static String minWindow(String s, String p) { int n = s.length(); int minLen = Integer.MAX_VALUE; String res = ""; // Generate all substrings // of the given string for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { String sub = s.substring(i, j + 1); // Check if the substring contains // all characters of the pattern if (hasAllChars(sub, p)) { int currLen = sub.length(); // Update the result if the current // substring is smaller if (currLen < minLen) { minLen = currLen; res = sub; } } } } return res; } public static void main(String[] args) { String s = "timetopractice"; String p = "toc"; String result = minWindow(s, p); if (!result.isEmpty()) System.out.println(result); else System.out.println(""); } } def hasallchars(s: str, p: str) -> bool: count = [0] * 256 # Count the frequency of each # character in the pattern for ch in p: count[ord(ch)] += 1 # For each character in the substring, # decrement its count for ch in s: if count[ord(ch)] > 0: count[ord(ch)] -= 1 # If all counts in the count array are zero, # the substring contains all characters of the pattern for val in count: if val > 0: return False return True # Function to find the smallest substring # containing all characters of the pattern def minWindow(s: str, p: str) -> str: n = len(s) minLen = float('inf') result = "" # Generate all substrings # of the given string for i in range(n): for j in range(i, n): sub = s[i:j + 1] # Check if the substring contains # all characters of the pattern if hasallchars(sub, p): currLen = len(sub) # Update the result if the current # substring is smaller if currLen < minLen: minLen = currLen result = sub return result if __name__ == "__main__": s = "timetopractice" p = "toc" res = minWindow(s, p) if res: print(res) else: print("") using System; class GfG { // Function to check if the substring contains // all characters of the pattern static bool hasAllChars(string s, string p){ int[] count = new int[256]; // Count the frequency of each // character in the pattern foreach (char ch in p) count[ch]++; // For each character in the substring, // decrement its count foreach (char ch in s){ if (count[ch] > 0) count[ch]--; } // If all counts in the count array are zero, // the substring contains all characters of the pattern for (int i = 0; i < 256; i++){ if (count[i] > 0) return false; } return true; } // Function to find the smallest substring // containing all characters of the pattern static string minWindow(string s, string p){ int n = s.Length; int minLen = int.MaxValue; string result = ""; // Generate all substrings // of the given string for (int i = 0; i < n; i++){ for (int j = i; j < n; j++){ string sub = s.Substring(i, j - i + 1); // Check if the substring contains // all characters of the pattern if (hasAllChars(sub, p)){ int currLen = sub.Length; // Update the result if the current // substring is smaller if (currLen < minLen){ minLen = currLen; result = sub; } } } } return result; } static void Main(){ string s = "timetopractice"; string p = "toc"; string res = minWindow(s, p); if (!string.IsNullOrEmpty(res)) Console.WriteLine(res); else Console.WriteLine(""); } } function hasAllChars(s, p) { const count = new Array(256).fill(0); // Count the frequency of each // character in the pattern for (let ch of p) { count[ch.charCodeAt(0)]++; } // For each character in the substring, // decrement its count for (let ch of s) { if (count[ch.charCodeAt(0)] > 0) { count[ch.charCodeAt(0)]--; } } // If all counts in the count array are zero, // the substring contains all characters of the pattern for (let val of count) { if (val > 0) { return false; } } return true; } // Function to find the smallest substring // containing all characters of the pattern function minWindow(s, p) { const n = s.length; let minLen = Infinity; let result = ""; // Generate all substrings // of the given string for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { const sub = s.substring(i, j + 1); // Check if the substring contains // all characters of the pattern if (hasAllChars(sub, p)) { const currLen = sub.length; // Update the result if the current // substring is smaller if (currLen < minLen) { minLen = currLen; result = sub; } } } } return result; } // Driver Code const s = "timetopractice"; const p = "toc"; const res = minWindow(s, p); if (res.length > 0) { console.log(res); } else { console.log("-1"); } [Better Approach] By using Binary Search on Answer - O(n*log(n)) Time and O(1) Space:
The idea is to check if a window of a certain size "mid" is valid (contains all characters of the p string), then all windows of size greater than "mid" will also be valid. Similarly, if a window of size "mid" is not valid, then all windows of size smaller than "mid" will also not be valid. This property allows us to apply binary search effectively.
Follow the steps below to solve the problem:
- Initialize low = 1 and high = string length. Denoting the minimum and maximum possible answer.
- For any value mid check if there is any substring of length mid in the string that contains all the characters of the P.
- If any such substring of length exists then store the starting index of that substring and update high to mid-1 and, check for substrings having lengths smaller than mid.
- Otherwise, if any such substring does not exist then update low to mid+1 and, check for substrings having lengths larger than mid.
C++ #include <iostream> #include <string> #include <climits> #include <cstring> using namespace std; bool isValid(string &s, string &p, int mid, int &start){ int count[256] = {0}; int distinct = 0; // Count the frequency of each character in p for (char x : p){ if (count[x] == 0) distinct++; count[x]++; } // Stores the number of characters in a substring of size // mid in s whose frequency is the same as the frequency in p int curr_count = 0; for (int i = 0; i < s.size(); i++){ count[s[i]]--; if (count[s[i]] == 0){ curr_count++; } if (i >= mid){ count[s[i - mid]]++; if (count[s[i - mid]] == 1){ curr_count--; } } if (i >= mid - 1){ // Substring of length mid found which contains // all the characters of p if (curr_count == distinct){ start = (i - mid) + 1; return true; } } } return false; } string smallestWindow(string s, string p){ int m = s.length(); int n = p.length(); // If s is smaller than p, it's impossible if (m < n) return "-1"; int minLength = INT_MAX; // Lower bound and Upper Bound for Binary Search // The smallest valid window size is n (size of p) int low = n, high = m; int idx = -1; while (low <= high){ int mid = (low + high) / 2; int start; if (isValid(s, p, mid, start)){ if (mid < minLength){ minLength = mid; idx = start; } high = mid - 1; } else{ low = mid + 1; } } if (idx == -1) return ""; return s.substr(idx, minLength); } int main(){ string s = "timetopractice"; string p = "toc"; cout << smallestWindow(s, p) << endl; return 0; } import java.util.HashMap; public class GfG { public static boolean isValid(String s, String p, int mid, int[] start){ int[] count = new int[256]; int distinct = 0; // Count the frequency of each character in p for (char x : p.toCharArray()) { if (count[x] == 0) distinct++; count[x]++; } int currCount = 0; for (int i = 0; i < s.length(); i++) { count[s.charAt(i)]--; if (count[s.charAt(i)] == 0) { currCount++; } if (i >= mid) { count[s.charAt(i - mid)]++; if (count[s.charAt(i - mid)] == 1) { currCount--; } } // If a valid substring is found if (i >= mid - 1 && currCount == distinct) { start[0] = i - mid + 1; return true; } } return false; } // Function to find the smallest window containing all // characters of p in s public static String smallestWindow(String s, String p){ int m = s.length(); int n = p.length(); // If s is smaller than p, it's impossible if (m < n) return "-1"; int minLength = Integer.MAX_VALUE; int low = n, high = m; int[] start = new int[1]; // Perform binary search to find the minimum window // size while (low <= high) { int mid = (low + high) / 2; if (isValid(s, p, mid, start)) { minLength = mid; high = mid - 1; } else { low = mid + 1; } } if (minLength == Integer.MAX_VALUE) return ""; return s.substring(start[0], start[0] + minLength); } public static void main(String[] args){ String s = "timetopractice"; String p = "toc"; System.out.println(smallestWindow(s, p)); } } def isValid(s, p, mid): count = [0] * 256 distinct = 0 # Count the frequency of each character in p for x in p: if count[ord(x)] == 0: distinct += 1 count[ord(x)] += 1 curr_count = 0 for i in range(len(s)): count[ord(s[i])] -= 1 if count[ord(s[i])] == 0: curr_count += 1 if i >= mid: count[ord(s[i - mid])] += 1 if count[ord(s[i - mid])] == 1: curr_count -= 1 if i >= mid - 1: # Substring of length mid found which contains # all the characters of p if curr_count == distinct: return True, i - mid + 1 return False, -1 def smallestWindow(s, p): m = len(s) n = len(p) # If s is smaller than p, it's impossible if m < n: return "-1" minLength = float('inf') low, high = n, m idx = -1 while low <= high: mid = (low + high) // 2 valid, start = isValid(s, p, mid) if valid: if mid < minLength: minLength = mid idx = start high = mid - 1 else: low = mid + 1 if idx == -1: return "" return s[idx:idx + minLength] if __name__ == "__main__": s = "timetopractice" p = "toc" print(smallestWindow(s, p)) using System; using System.Collections.Generic; using System.Linq; class GfG { static bool IsValid(string s, string p, int mid, out int start){ int[] count = new int[256]; Array.Fill(count, 0); int distinct = 0; // Count the frequency of each character in p foreach(char x in p) { if (count[x] == 0) distinct++; count[x]++; } // Stores the number of characters in a substring of // size mid in s whose frequency is the same as the // frequency in p int currCount = 0; start = -1; for (int i = 0; i < s.Length; i++) { count[s[i]]--; if (count[s[i]] == 0) { currCount++; } if (i >= mid) { count[s[i - mid]]++; if (count[s[i - mid]] == 1) { currCount--; } } if (i >= mid - 1) { // Substring of length mid found which // contains all the characters of p if (currCount == distinct) { start = (i - mid) + 1; return true; } } } return false; } static string SmallestWindow(string s, string p){ int m = s.Length; int n = p.Length; // If s is smaller than p, it's impossible if (m < n) return "-1"; int minLength = int.MaxValue; // Lower bound and Upper Bound for Binary Search // The smallest valid window size is n (size of p) int low = n, high = m; int idx = -1; while (low <= high) { int mid = (low + high) / 2; int start; if (IsValid(s, p, mid, out start)) { if (mid < minLength) { minLength = mid; idx = start; } high = mid - 1; } else { low = mid + 1; } } if (idx == -1) return ""; return s.Substring(idx, minLength); } static void Main(){ string s = "timetopractice"; string p = "toc"; Console.WriteLine(SmallestWindow(s, p)); } } function isValid(s, p, mid){ const count = new Array(256).fill(0); let distinct = 0; // Count the frequency of each character in p for (let x of p) { if (count[x.charCodeAt(0)] === 0) distinct++; count[x.charCodeAt(0)]++; } // Stores the number of characters in a substring of // size mid in s whose frequency is the same as the // frequency in p let currCount = 0; let start = -1; for (let i = 0; i < s.length; i++) { count[s[i].charCodeAt(0)]--; if (count[s[i].charCodeAt(0)] === 0) { currCount++; } if (i >= mid) { count[s[i - mid].charCodeAt(0)]++; if (count[s[i - mid].charCodeAt(0)] === 1) { currCount--; } } if (i >= mid - 1) { // Substring of length mid found which contains // all the characters of p if (currCount === distinct) { start = (i - mid) + 1; return start; } } } return -1; } function smallestWindow(s, p){ const m = s.length; const n = p.length; // If s is smaller than p, it's impossible if (m < n) return "-1"; let minLength = Infinity; // Lower bound and Upper Bound for Binary Search // The smallest valid window size is n (size of p) let low = n, high = m; let idx = -1; while (low <= high) { const mid = Math.floor((low + high) / 2); const start = isValid(s, p, mid); if (start !== -1) { if (mid < minLength) { minLength = mid; idx = start; } high = mid - 1; } else { low = mid + 1; } } if (idx === -1) return ""; return s.substring(idx, idx + minLength); } // Driver Code const s = "timetopractice"; const p = "toc"; console.log(smallestWindow(s, p)); [Expected Approach] Using Window Sliding - O(n) Time and O(1) Space:
The idea is to use Window Sliding (start and j) to maintain a sliding window over string S, while tracking character frequencies with two count arrays:
- Initialize:
- A count array to store the frequency of characters in
P. - Another count array to track the characters in the current window of
S. - Variables to track the minimum window length and its start index.
- Expand the Window:
- Move the
j pointer through S, updating the window's character counts. - When all characters of
P are present in the window, a valid window is found.
- Shrink the Window before updating result
- Move the
start pointer right to minimize the window while ensuring all characters from P remain in the window. - Track the smallest window during this process.
- Return Result:
- If a valid window is found, return the smallest substring. If no valid window exists, return
"-1".
Illustration:
C++ #include <iostream> #include <string> #include <vector> #include <climits> using namespace std; string smallestWindow(string s, string p){ int len1 = s.length(); int len2 = p.length(); if (len1 < len2) return ""; vector<int> countP(256, 0); vector<int> countS(256, 0); // Store occurrence of characters of P for (int i = 0; i < len2; i++) countP[p[i]]++; int start = 0, start_idx = -1, min_len = INT_MAX; int count = 0; for (int j = 0; j < len1; j++){ // Count occurrence of characters // of string S countS[s[j]]++; // If S's char matches with P's char, // increment count if (countP[s[j]] != 0 && countS[s[j]] <= countP[s[j]]){ count++; } // If all characters are matched if (count == len2){ // Try to minimize the window while (countS[s[start]] > countP[s[start]] || countP[s[start]] == 0){ if (countS[s[start]] > countP[s[start]]){ countS[s[start]]--; } start++; } // Update window size int len = j - start + 1; if (min_len > len){ min_len = len; start_idx = start; } } } if (start_idx == -1) return ""; return s.substr(start_idx, min_len); } int main(){ string s = "timetopractice"; string p = "toc"; string res = smallestWindow(s, p); cout << res; return 0; } class GfG { public static String smallestWindow(String s, String p) { int len1 = s.length(); int len2 = p.length(); if (len1 < len2) return "-1"; int[] countP = new int[256]; int[] countS = new int[256]; // Store occurrence of characters of P for (int i = 0; i < len2; i++) countP[p.charAt(i)]++; int start = 0, start_idx = -1, min_len = Integer.MAX_VALUE; int count = 0; for (int j = 0; j < len1; j++) { char currChar = s.charAt(j); // Count occurrence of characters of string S countS[currChar]++; // If S's char matches with P's char, increment count if (countP[currChar] > 0 && countS[currChar] <= countP[currChar]) { count++; } // If all characters are matched if (count == len2) { // Try to minimize the window char startChar; while (countS[startChar = s.charAt(start)] > countP[startChar] || countP[startChar] == 0) { if (countS[startChar] > countP[startChar]) { countS[startChar]--; } start++; } // Update window size int len = j - start + 1; if (min_len > len) { min_len = len; start_idx = start; } } } if (start_idx == -1) return ""; return s.substring(start_idx, start_idx + min_len); } public static void main(String[] args) { String s = "timetopractice"; String p = "toc"; String res = smallestWindow(s, p); System.out.println(res); } } def smallestWindow(s, p): len1 = len(s) len2 = len(p) if len1 < len2: return "-1" countP = [0] * 256 countS = [0] * 256 # Store occurrence of characters of P for char in p: countP[ord(char)] += 1 start = 0 start_idx = -1 min_len = float('inf') count = 0 for j in range(len1): # Count occurrence of characters of string S countS[ord(s[j])] += 1 # If S's char matches with P's char, increment count if countP[ord(s[j])] != 0 and countS[ord(s[j])] <= countP[ord(s[j])]: count += 1 # If all characters are matched if count == len2: # Try to minimize the window while countS[ord(s[start])] > countP[ord(s[start])] or countP[ord(s[start])] == 0: if countS[ord(s[start])] > countP[ord(s[start])]: countS[ord(s[start])] -= 1 start += 1 # Update window size length = j - start + 1 if min_len > length: min_len = length start_idx = start if start_idx == -1: return "-1" return s[start_idx:start_idx + min_len] s = "timetopractice" p = "toc" res = smallest_window(s, p) print(res) using System; using System.Collections.Generic; class GfG { public static string smallestWindow(string s, string p) { int len1 = s.Length; int len2 = p.Length; if (len1 < len2) return "-1"; int[] countP = new int[256]; int[] countS = new int[256]; // Store occurrence of characters of P for (int i = 0; i < len2; i++) countP[p[i]]++; int start = 0, start_idx = -1, min_len = int.MaxValue; int count = 0; for (int j = 0; j < len1; j++) { char currChar = s[j]; // Count occurrence of characters of string S countS[currChar]++; // If S's char matches with P's char, increment count if (countP[currChar] > 0 && countS[currChar] <= countP[currChar]) { count++; } // If all characters are matched if (count == len2) { // Try to minimize the window char startChar; while (countS[startChar = s[start]] > countP[startChar] || countP[startChar] == 0) { if (countS[startChar] > countP[startChar]) { countS[startChar]--; } start++; } // Update window size int len = j - start + 1; if (min_len > len) { min_len = len; start_idx = start; } } } if (start_idx == -1) return ""; return s.Substring(start_idx, min_len); } public static void Main(string[] args) { string s = "timetopractice"; string p = "toc"; string res = SmallestWindowFunc(s, p); Console.WriteLine(res); } } function smallestWindow(s, p) { let len1 = s.length; let len2 = p.length; if (len1 < len2) { return "-1"; } let countP = new Array(256).fill(0); let countS = new Array(256).fill(0); // Store occurrence of characters of P for (let char of p) { countP[char.charCodeAt(0)]++; } let start = 0; let startIdx = -1; let minLen = Infinity; let count = 0; for (let j = 0; j < len1; j++) { // Count occurrence of characters of string S countS[s.charCodeAt(j)]++; // If S's char matches with P's char, increment count if (countP[s.charCodeAt(j)] !== 0 && countS[s.charCodeAt(j)] <= countP[s.charCodeAt(j)]) { count++; } // If all characters are matched if (count === len2) { // Try to minimize the window while (countS[s.charCodeAt(start)] > countP[s.charCodeAt(start)] || countP[s.charCodeAt(start)] === 0) { if (countS[s.charCodeAt(start)] > countP[s.charCodeAt(start)]) { countS[s.charCodeAt(start)]--; } start++; } // Update window size let length = j - start + 1; if (minLen > length) { minLen = length; startIdx = start; } } } if (startIdx === -1) { return ""; } return s.substring(startIdx, startIdx + minLen); } // Driver Code let s = "timetopractice"; let p = "toc"; let result = smallestWindow(s, p); console.log(result); Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem