Smallest window in a String containing all characters of other String
Given two strings, string, and pattern, the task is to find the smallest substring in string containing all characters of pattern.
Examples:
Input: string = “this is a test string”, pattern = “tist”
Output: “t stri”
Explanation: “t stri” contains all the characters of pattern.Input: string = “w3wiki”, pattern = “ork”
Output: “ksfor”
Smallest window in a String containing all characters of other String by generating all substrings:
- Generate all substrings of string.
- For each substring, check whether the substring contains all characters of pattern (“tist”)
- Finally, print the smallest substring containing all characters of pattern.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Function to check if the substring contains all // characters of the pattern bool containsAllCharacters(string& substr, string& pattern) { int count[256] = { 0 }; // Count the frequency of each character in the pattern for ( char ch : pattern) count[ch]++; // For each character in the substring, decrement its // count for ( char ch : substr) { 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 findSmallestSubstring(string& str, string& pattern) { int len_str = str.length(); int len_pattern = pattern.length(); string smallestSubstring = "" ; int minLength = INT_MAX; // Generate all substrings of the given string for ( int i = 0; i < len_str; i++) { for ( int j = i; j < len_str; j++) { string substr = str.substr(i, j - i + 1); // Check if the substring contains all // characters of the pattern if (containsAllCharacters(substr, pattern)) { int currentLength = substr.length(); // Update the smallestSubstring if the // current substring is smaller if (currentLength < minLength) { minLength = currentLength; smallestSubstring = substr; } } } } return smallestSubstring; } int main() { string str1 = "this is a test string" ; string pattern1 = "tist" ; cout << "Input: string = \"" << str1 << "\", pattern = \"" << pattern1 << "\"" << endl; cout << "Output: \"" << findSmallestSubstring(str1, pattern1) << "\"" << endl; string str2 = "w3wiki" ; string pattern2 = "ork" ; cout << "Input: string = \"" << str2 << "\", pattern = \"" << pattern2 << "\"" << endl; cout << "Output: \"" << findSmallestSubstring(str2, pattern2) << "\"" << endl; return 0; } |
Java
import java.util.Arrays; public class SubstringContainingPattern { // Function to check if the substring contains all // characters of the pattern static boolean containsAllCharacters(String substr, String pattern) { int [] count = new int [ 256 ]; // Count the frequency of each character in the pattern for ( char ch : pattern.toCharArray()) count[ch]++; // For each character in the substring, decrement its // count for ( char ch : substr.toCharArray()) { 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 findSmallestSubstring(String str, String pattern) { int lenStr = str.length(); int lenPattern = pattern.length(); String smallestSubstring = "" ; int minLength = Integer.MAX_VALUE; // Generate all substrings of the given string for ( int i = 0 ; i < lenStr; i++) { for ( int j = i; j < lenStr; j++) { String substr = str.substring(i, j + 1 ); // Check if the substring contains all // characters of the pattern if (containsAllCharacters(substr, pattern)) { int currentLength = substr.length(); // Update the smallestSubstring if the // current substring is smaller if (currentLength < minLength) { minLength = currentLength; smallestSubstring = substr; } } } } return smallestSubstring; } public static void main(String[] args) { String str1 = "this is a test string" ; String pattern1 = "tist" ; System.out.println( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ); System.out.println( "Output: \"" + findSmallestSubstring(str1, pattern1) + "\"" ); String str2 = "w3wiki" ; String pattern2 = "ork" ; System.out.println( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ); System.out.println( "Output: \"" + findSmallestSubstring(str2, pattern2) + "\"" ); } } // This code is contributed by shivamgupta0987654321 |
Python
# Function to check if the substring contains all # characters of the pattern def containsAllCharacters(substr, pattern): count = [ 0 ] * 256 # Count the frequency of each character in the pattern for ch in pattern: count[ ord (ch)] + = 1 # For each character in the substring, decrement its count for ch in substr: 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 i in range ( 256 ): if count[i] > 0 : return False return True # Function to find the smallest substring containing all # characters of the pattern def findSmallestSubstring(s, pattern): len_str = len (s) len_pattern = len (pattern) smallestSubstring = "" minLength = float ( 'inf' ) # Generate all substrings of the given string for i in range (len_str): for j in range (i, len_str): substr = s[i:j + 1 ] # Check if the substring contains all # characters of the pattern if containsAllCharacters(substr, pattern): currentLength = len (substr) # Update the smallestSubstring if the # current substring is smaller if currentLength < minLength: minLength = currentLength smallestSubstring = substr return smallestSubstring if __name__ = = "__main__" : str1 = "this is a test string" pattern1 = "tist" print ( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ) print ( "Output: \"" + findSmallestSubstring(str1, pattern1) + "\"" ) str2 = "w3wiki" pattern2 = "ork" print ( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ) print ( "Output: \"" + findSmallestSubstring(str2, pattern2) + "\"" ) |
C#
using System; class Program { // Function to check if the substring contains all // characters of the pattern static bool ContainsAllCharacters( string substr, string pattern) { int [] count = new int [256]; // Count the frequency of each character in the pattern foreach ( char ch in pattern) count[ch]++; // For each character in the substring, decrement its // count foreach ( char ch in substr) { if (count[ch] > 0) count[ch]--; } // If all counts in the count array are zero, the // substring contains all characters of the pattern foreach ( int val in count) { if (val > 0) return false ; } return true ; } // Function to find the smallest substring containing all // characters of the pattern static string FindSmallestSubstring( string str, string pattern) { int lenStr = str.Length; int lenPattern = pattern.Length; string smallestSubstring = "" ; int minLength = int .MaxValue; // Generate all substrings of the given string for ( int i = 0; i < lenStr; i++) { for ( int j = i; j < lenStr; j++) { string substr = str.Substring(i, j - i + 1); // Check if the substring contains all // characters of the pattern if (ContainsAllCharacters(substr, pattern)) { int currentLength = substr.Length; // Update the smallestSubstring if the // current substring is smaller if (currentLength < minLength) { minLength = currentLength; smallestSubstring = substr; } } } } return smallestSubstring; } static void Main( string [] args) { string str1 = "this is a test string" ; string pattern1 = "tist" ; Console.WriteLine( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ); Console.WriteLine( "Output: \"" + FindSmallestSubstring(str1, pattern1) + "\"" ); string str2 = "w3wiki" ; string pattern2 = "ork" ; Console.WriteLine( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ); Console.WriteLine( "Output: \"" + FindSmallestSubstring(str2, pattern2) + "\"" ); } } |
Javascript
// Function to check if the substring contains all // characters of the pattern function containsAllCharacters(substr, pattern) { let count = Array(256).fill(0); // Count the frequency of each character in the pattern for (let c of pattern) { count++; } // For each character in the substring, decrement its count for (let c of substr) { if (count > 0) { count--; } } // If all counts in the count array are zero, the // substring contains all characters of the pattern for (let 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 function findSmallestSubstring(str, pattern) { let len_str = str.length; let len_pattern = pattern.length; let smallestSubstring = "" ; let minLength = Number.MAX_VALUE; // Generate all substrings of the given string for (let i = 0; i < len_str; i++) { for (let j = i; j < len_str; j++) { let substr = str.substring(i, j + 1); // Check if the substring contains all characters of the pattern if (containsAllCharacters(substr, pattern)) { let currentLength = substr.length; // Update the smallestSubstring if the current substring is smaller if (currentLength < minLength) { minLength = currentLength; smallestSubstring = substr; } } } } return smallestSubstring; } // Driver code let str1 = "this is a test string" ; let pattern1 = "tist" ; console.log(`Input: string = "${str1}" , pattern = "${pattern1}" `); console.log(`Output: "${findSmallestSubstring(str1, pattern1)}" `); let str2 = "w3wiki" ; let pattern2 = "ork" ; console.log(`Input: string = "${str2}" , pattern = "${pattern2}" `); console.log(`Output: "${findSmallestSubstring(str2, pattern2)}" `); |
Input: string = "this is a test string", pattern = "tist" Output: "t stri" Input: string = "w3wiki", pattern = "ork" Output: "ksfor"
Time Complexity: O(N3)
Auxiliary Space: O(N) to create substrings.
Smallest window in a String containing all characters of other String using Binary Search on Answer:
The idea is to check if a window of a certain size “mid” is valid (contains all characters of the “pattern” 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 and high as 1 and string length respectively 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 pattern.
- 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.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Function to check if any substring of length mid contains // all characters of the pattern bool isValid(string& str, string& pattern, int mid, int & start) { // Count the frequency of each character in the pattern int count[256] = { 0 }; // Stores number of distinct characters in pattern int distinct = 0; bool found = false ; // Count the frequency of each character in the pattern for ( char x : pattern) { count[x]++; if (count[x] == 1) distinct++; } // Stores the number of charcters in a substring of size // mid in str whose frequency is same as frequency in // pattern int curr_count = 0; for ( int i = 0; i < str.size(); i++) { count[str[i]]--; if (count[str[i]] == 0) { curr_count++; } if (i >= mid) { count[str[i - mid]]++; if (count[str[i - mid]] == 1) { curr_count--; } } if (i >= mid - 1) { // Substring of length mid found which contains // all the characters of pattern if (curr_count == distinct) { found = true ; // Stores starting index of that substring start = (i - mid) + 1; break ; } } } return found; } // Function to find the smallest substring containing all // characters of the pattern string findSmallestSubstring(string& str, string& pattern) { int len_str = str.length(); int len_pattern = pattern.length(); string smallestSubstring = "" ; int minLength = INT_MAX; // Lower bound and Upper Bound for Binary Serach int low_bound = 1, high_bound = len_str; // Stores starting index of min length substring int idx; // Applying Binary Search on answer while (low_bound <= high_bound) { int mid = (low_bound + high_bound) / 2; int start; // If a substring of length mid is found which // contains all teh characters of pattern then // update minLenght and high_bound otherwise update // low_bound if (isValid(str, pattern, mid, start)) { if (mid < minLength) { minLength = mid; idx = start; } high_bound = mid - 1; } else { low_bound = mid + 1; } } return smallestSubstring = str.substr(idx, minLength); } int main() { string str1 = "this is a test string" ; string pattern1 = "tist" ; cout << "Input: string = \"" << str1 << "\", pattern = \"" << pattern1 << "\"" << endl; cout << "Output: \"" << findSmallestSubstring(str1, pattern1) << "\"" << endl; string str2 = "w3wiki" ; string pattern2 = "ork" ; cout << "Input: string = \"" << str2 << "\", pattern = \"" << pattern2 << "\"" << endl; cout << "Output: \"" << findSmallestSubstring(str2, pattern2) << "\"" << endl; return 0; } |
Java
import java.util.Arrays; public class GFG { // Function to check if any substring of length mid contains // all characters of the pattern static boolean isValid(String str, String pattern, int mid, int [] start) { // Count the frequency of each character in the pattern int [] count = new int [ 256 ]; // Stores number of distinct characters in pattern int distinct = 0 ; boolean found = false ; // Count the frequency of each character in the pattern for ( char c : pattern.toCharArray()) { count++; if (count == 1 ) distinct++; } // Stores the number of characters in a substring of size // mid in str whose frequency is the same as the frequency in // pattern int currCount = 0 ; for ( int i = 0 ; i < str.length(); i++) { count[str.charAt(i)]--; if (count[str.charAt(i)] == 0 ) { currCount++; } if (i >= mid) { count[str.charAt(i - mid)]++; if (count[str.charAt(i - mid)] == 1 ) { currCount--; } } if (i >= mid - 1 ) { // Substring of length mid found which contains // all the characters of the pattern if (currCount == distinct) { found = true ; // Stores the starting index of that substring start[ 0 ] = (i - mid) + 1 ; break ; } } } return found; } // Function to find the smallest substring containing all // characters of the pattern static String findSmallestSubstring(String str, String pattern) { int lenStr = str.length(); int lenPattern = pattern.length(); String smallestSubstring = "" ; int minLength = Integer.MAX_VALUE; // Lower bound and Upper Bound for Binary Search int lowBound = 1 , highBound = lenStr; // Stores starting index of min length substring int [] idx = new int [ 1 ]; // Applying Binary Search on answer while (lowBound <= highBound) { int mid = (lowBound + highBound) / 2 ; int [] start = new int [ 1 ]; // If a substring of length mid is found which // contains all the characters of the pattern then // update minLength and highBound, otherwise update // lowBound if (isValid(str, pattern, mid, start)) { if (mid < minLength) { minLength = mid; idx[ 0 ] = start[ 0 ]; } highBound = mid - 1 ; } else { lowBound = mid + 1 ; } } return smallestSubstring = str.substring(idx[ 0 ], idx[ 0 ] + minLength); } public static void main(String[] args) { String str1 = "this is a test string" ; String pattern1 = "tist" ; System.out.println( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ); System.out.println( "Output: \"" + findSmallestSubstring(str1, pattern1) + "\"" ); String str2 = "w3wiki" ; String pattern2 = "ork" ; System.out.println( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ); System.out.println( "Output: \"" + findSmallestSubstring(str2, pattern2) + "\"" ); } } |
C#
using System; class SmallestWindowSubstring { // Function to check if a valid window of size "mid" // exists static bool IsValid( string str, string pattern, int mid, ref int start) { int lenStr = str.Length; int lenPattern = pattern.Length; int [] count = new int [256]; int distinct = 0; bool found = false ; for ( int i = 0; i < lenPattern; i++) { if (count[pattern[i]] == 0) distinct++; count[pattern[i]]++; } int currCount = 0; for ( int i = 0; i < lenStr; i++) { count[str[i]]--; if (count[str[i]] == 0) currCount++; if (i >= mid) { count[str[i - mid]]++; if (count[str[i - mid]] == 1) currCount--; } if (i >= mid - 1) { if (currCount == distinct) { found = true ; start = i - mid + 1; break ; } } } return found; } // Function to find the smallest window containing all // characters of pattern static string FindSmallestWindowSubstring( string str, string pattern) { int lenStr = str.Length; int lenPattern = pattern.Length; string smallestSubstring = "" ; int minLength = int .MaxValue; int low = 1; int high = lenStr; int idx = 0; while (low <= high) { int mid = (low + high) / 2; int start = 0; if (IsValid(str, pattern, mid, ref start)) { if (mid < minLength) { minLength = mid; idx = start; } high = mid - 1; } else { low = mid + 1; } } if (minLength != int .MaxValue) { smallestSubstring = str.Substring(idx, minLength); } return smallestSubstring; } static void Main() { string str1 = "this is a test string" ; string pattern1 = "tist" ; Console.WriteLine( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ); Console.WriteLine( "Output: \"" + FindSmallestWindowSubstring(str1, pattern1) + "\"" ); string str2 = "w3wiki" ; string pattern2 = "ork" ; Console.WriteLine( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ); Console.WriteLine( "Output: \"" + FindSmallestWindowSubstring(str2, pattern2) + "\"" ); } } |
Javascript
// Function to check if any substring of length mid contains // all characters of the pattern function isValid(str, pattern, mid, start) { // Count the frequency of each character in the pattern const count = new Array(256).fill(0); // Stores the number of distinct characters in the pattern let distinct = 0; let found = false ; // Count the frequency of each character in the pattern for (const c of pattern) { count++; if (count === 1) { distinct++; } } // Stores the number of characters in a substring of size // mid in str whose frequency is the same as the frequency in // the pattern let curr_count = 0; for (let i = 0; i < str.length; i++) { count[str.charCodeAt(i)]--; if (count[str.charCodeAt(i)] === 0) { curr_count++; } if (i >= mid) { count[str.charCodeAt(i - mid)]++; if (count[str.charCodeAt(i - mid)] === 1) { curr_count--; } } if (i >= mid - 1) { // Substring of length mid found which contains // all the characters of the pattern if (curr_count === distinct) { found = true ; // Stores the starting index of that substring start[0] = (i - mid) + 1; break ; } } } return found; } // Function to find the smallest substring containing all // characters of the pattern function findSmallestSubstring(str, pattern) { const len_str = str.length; const len_pattern = pattern.length; let smallestSubstring = "" ; let minLength = Infinity; // Lower bound and Upper Bound for Binary Search let low_bound = 1; let high_bound = len_str; // Stores the starting index of the minimum length substring const idx = [0]; // Applying Binary Search on the answer while (low_bound <= high_bound) { const mid = Math.floor((low_bound + high_bound) / 2); let start = [0]; // If a substring of length mid is found which // contains all the characters of the pattern, then // update minLength and high_bound; otherwise, update // low_bound if (isValid(str, pattern, mid, start)) { if (mid < minLength) { minLength = mid; idx[0] = start[0]; } high_bound = mid - 1; } else { low_bound = mid + 1; } } smallestSubstring = str.substr(idx[0], minLength); return smallestSubstring; } // Driver Code const str1 = "this is a test string" ; const pattern1 = "tist" ; console.log( "Input: string = \"" + str1 + "\", pattern = \"" + pattern1 + "\"" ); console.log( "Output: \"" + findSmallestSubstring(str1, pattern1) + "\"" ); const str2 = "w3wiki" ; const pattern2 = "ork" ; console.log( "Input: string = \"" + str2 + "\", pattern = \"" + pattern2 + "\"" ); console.log( "Output: \"" + findSmallestSubstring(str2, pattern2) + "\"" ); |
Python3
# Function to check if any substring of length mid contains # all characters of the pattern def is_valid(s, pattern, mid, start): # Count the frequency of each character in the pattern count = [ 0 ] * 256 # Stores the number of distinct characters in the pattern distinct = 0 found = False # Count the frequency of each character in the pattern for c in pattern: count[ ord (c)] + = 1 if count[ ord (c)] = = 1 : distinct + = 1 # Stores the number of characters in a substring of size # mid in s whose frequency is the same as the frequency in # the pattern 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 the pattern if curr_count = = distinct: found = True # Stores the starting index of that substring start[ 0 ] = i - mid + 1 break return found # Function to find the smallest substring containing all # characters of the pattern def find_smallest_substring(s, pattern): len_str = len (s) len_pattern = len (pattern) smallest_substring = "" min_length = float ( 'inf' ) # Lower bound and Upper Bound for Binary Search low_bound = 1 high_bound = len_str # Stores the starting index of the min length substring idx = [ 0 ] # Applying Binary Search on answer while low_bound < = high_bound: mid = (low_bound + high_bound) / / 2 start = [ 0 ] # If a substring of length mid is found which # contains all the characters of the pattern then # update min_length and high_bound; otherwise, update # low_bound if is_valid(s, pattern, mid, start): if mid < min_length: min_length = mid idx[ 0 ] = start[ 0 ] high_bound = mid - 1 else : low_bound = mid + 1 smallest_substring = s[idx[ 0 ]:idx[ 0 ] + min_length] return smallest_substring if __name__ = = "__main__" : str1 = "this is a test string" pattern1 = "tist" print ( "Input: string =" , str1, ", pattern =" , pattern1) print ( "Output:" , '"' + find_smallest_substring(str1, pattern1) + '"' ) str2 = "w3wiki" pattern2 = "ork" print ( "Input: string =" , str2, ", pattern =" , pattern2) print ( "Output:" , '"' + find_smallest_substring(str2, pattern2) + '"' ) |
Input: string = "this is a test string", pattern = "tist" Output: "t stri" Input: string = "w3wiki", pattern = "ork" Output: "ksfor"
Time Complexity: O(N*logN), where N is the length of string.
Auxiliary Space: O(1)
Smallest window in a String containing all characters of other String using Two Pointers and Hashing:
The idea is to use the two pointer approach on the hash array of pattern string and then find the minimum window by eliminating characters from the start of the window.
Follow the steps below to solve the problem:
- First check if the length of the string is less than the length of the given pattern, if yes then “no such window can exist “.
- Store the occurrence of characters of the given pattern in a hash array (say, hash_pat[]).
- We will be using two pointer technique here
- Start matching the characters of the pattern with the characters of the string i.e. increment count if a character matches.
- Check if (count == length of pattern ) this means a window is found.
- If such a window is found, try to minimize it by removing extra characters from the beginning of the current window.
- Delete one character from the first and again find this deleted key at right.
- If found, then again check if the count and pattern length are the same and repeat the process.
- Update min_length.
- Print the minimum length window.
Illustration:
Below is the implementation of the above approach.
C++
// C++ program to find // smallest window containing // all characters of a pattern. #include <bits/stdc++.h> using namespace std; const int no_of_chars = 256; // Function to find smallest // window containing // all characters of 'pat' string findSubString(string str, string pat) { int len1 = str.length(); int len2 = pat.length(); // Check if string's length // is less than pattern's // length. If yes then no such // window can exist if (len1 < len2) { cout << "No such window exists" ; return "" ; } int hash_pat[no_of_chars] = { 0 }; int hash_str[no_of_chars] = { 0 }; // Store occurrence ofs characters // of pattern for ( int i = 0; i < len2; i++) hash_pat[pat[i]]++; int start = 0, start_index = -1, min_len = INT_MAX; // Start traversing the string // Count of characters int count = 0; for ( int j = 0; j < len1; j++) { // Count occurrence of characters // of string hash_str[str[j]]++; // If string's char matches with // pattern's char // then increment count if (hash_str[str[j]] <= hash_pat[str[j]]) count++; // if all the characters are matched if (count == len2) { // Try to minimize the window while (hash_str[str[start]] > hash_pat[str[start]] || hash_pat[str[start]] == 0) { if (hash_str[str[start]] > hash_pat[str[start]]) hash_str[str[start]]--; start++; } // update window size int len_window = j - start + 1; if (min_len > len_window) { min_len = len_window; start_index = start; } } } // If no window found if (start_index == -1) { cout << "No such window exists" ; return "" ; } // Return substring starting from start_index // and length min_len return str.substr(start_index, min_len); } // Driver code int main() { string str1 = "this is a test string" ; string pattern1 = "tist" ; cout << "Input: string = \"" << str1 << "\", pattern = \"" << pattern1 << "\"" << endl; cout << "Output: \"" << findSubString(str1, pattern1) << "\"" << endl; string str2 = "w3wiki" ; string pattern2 = "ork" ; cout << "Input: string = \"" << str2 << "\", pattern = \"" << pattern2 << "\"" << endl; cout << "Output: \"" << findSubString(str2, pattern2) << "\"" << endl; return 0; } |
Java
// Java program to find smallest // window containing // all characters of a pattern. public class GFG { static final int no_of_chars = 256 ; // Function to find smallest // window containing // all characters of 'pat' static String findSubString(String str, String pat) { int len1 = str.length(); int len2 = pat.length(); // Check if string's length is // less than pattern's // length. If yes then no such // window can exist if (len1 < len2) { System.out.println( "No such window exists" ); return "" ; } int hash_pat[] = new int [no_of_chars]; int hash_str[] = new int [no_of_chars]; // Store occurrence ofs // characters of pattern for ( int i = 0 ; i < len2; i++) hash_pat[pat.charAt(i)]++; int start = 0 , start_index = - 1 , min_len = Integer.MAX_VALUE; // Start traversing the string // Count of characters int count = 0 ; for ( int j = 0 ; j < len1; j++) { // Count occurrence of characters // of string hash_str[str.charAt(j)]++; // If string's char matches // with pattern's char // then increment count if (hash_str[str.charAt(j)] <= hash_pat[str.charAt(j)]) count++; // If all the characters are matched if (count == len2) { // Try to minimize the window while (hash_str[str.charAt(start)] > hash_pat[str.charAt(start)] || hash_pat[str.charAt(start)] == 0 ) { if (hash_str[str.charAt(start)] > hash_pat[str.charAt(start)]) hash_str[str.charAt(start)]--; start++; } // update window size int len_window = j - start + 1 ; if (min_len > len_window) { min_len = len_window; start_index = start; } } } // If no window found if (start_index == - 1 ) { System.out.println( "No such window exists" ); return "" ; } // Return substring starting // from start_index // and length min_len return str.substring(start_index, start_index + min_len); } // Driver Method public static void main(String[] args) { String str = "this is a test string" ; String pat = "tist" ; System.out.print(findSubString(str, pat)); } } |
C#
// C# program to find smallest // window containing // all characters of a pattern. using System; class GFG { static int no_of_chars = 256; // Function to find smallest // window containing // all characters of 'pat' static String findSubString(String str, String pat) { int len1 = str.Length; int len2 = pat.Length; // Check if string's length is // less than pattern's // length. If yes then no such // window can exist if (len1 < len2) { Console.WriteLine( "No such window exists" ); return "" ; } int [] hash_pat = new int [no_of_chars]; int [] hash_str = new int [no_of_chars]; // Store occurrence ofs characters // of pattern for ( int i = 0; i < len2; i++) hash_pat[pat[i]]++; int start = 0, start_index = -1, min_len = int .MaxValue; // Start traversing the string // Count of characters int count = 0; for ( int j = 0; j < len1; j++) { // Count occurrence of characters // of string hash_str[str[j]]++; // If string's char matches // with pattern's char // then increment count if (hash_str[str[j]] <= hash_pat[str[j]]) count++; // if all the characters are matched if (count == len2) { // Try to minimize the window while (hash_str[str[start]] > hash_pat[str[start]] || hash_pat[str[start]] == 0) { if (hash_str[str[start]] > hash_pat[str[start]]) hash_str[str[start]]--; start++; } // update window size int len_window = j - start + 1; if (min_len > len_window) { min_len = len_window; start_index = start; } } } // If no window found if (start_index == -1) { Console.WriteLine( "No such window exists" ); return "" ; } // Return substring starting from start_index // and length min_len return str.Substring(start_index, min_len); } // Driver Method public static void Main(String[] args) { String str = "this is a test string" ; String pat = "tist" ; Console.WriteLine(findSubString(str, pat)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // javascript program to find smallest // window containing // all characters of a pattern. var no_of_chars = 256; // Function to find smallest // window containing // all characters of 'pat' function findSubString(str, pat) { var len1 = str.length; var len2 = pat.length; // Check if string's length is // less than pattern's // length. If yes then no such // window can exist if (len1 < len2) { document.write( "No such window exists" ); return "" ; } var hash_pat = Array.from({length: no_of_chars}, (_, i) => 0); var hash_str = Array.from({length: no_of_chars}, (_, i) => 0); // Store occurrence ofs // characters of pattern for ( var i = 0; i < len2; i++) hash_pat[pat.charAt(i).charCodeAt(0)]++; var start = 0, start_index = -1, min_len = Number.MAX_VALUE; // Start traversing the string // Count of characters var count = 0; for ( var j = 0; j < len1; j++) { // Count occurrence of characters // of string hash_str[str.charAt(j).charCodeAt(0)]++; // If string's char matches // with pattern's char // then increment count if (hash_str[str.charAt(j).charCodeAt(0)] <= hash_pat[str.charAt(j).charCodeAt(0)]) count++; // If all the characters are matched if (count == len2) { // Try to minimize the window while (hash_str[str.charAt(start).charCodeAt(0)] > hash_pat[str.charAt(start).charCodeAt(0)] || hash_pat[str.charAt(start).charCodeAt(0)] == 0) { if (hash_str[str.charAt(start).charCodeAt(0)] > hash_pat[str.charAt(start).charCodeAt(0)]) hash_str[str.charAt(start).charCodeAt(0)]--; start++; } // update window size var len_window = j - start + 1; if (min_len > len_window) { min_len = len_window; start_index = start; } } } // If no window found if (start_index == -1) { document.write( "No such window exists" ); return "" ; } // Return substring starting // from start_index // and length min_len return str.substring(start_index, start_index + min_len); } // Driver Method var str = "this is a test string" ; var pat = "tist" ; document.write(findSubString(str, pat)); // This code is contributed by 29AjayKumar </script> |
PHP
<?php // PHP program to find smallest window // containing all characters of a pattern. define( "no_of_chars" , 256); // Function to find smallest window // containing all characters of 'pat' function findSubString(& $str , & $pat ) { $len1 = strlen ( $str ); $len2 = strlen ( $pat ); // check if string's length is less // than pattern's length. If yes // then no such window can exist if ( $len1 < $len2 ) { echo "No such window exists" ; return "" ; } $hash_pat = array_fill (0, no_of_chars, 0); $hash_str = array_fill (0, no_of_chars, 0); // store occurrence ofs characters // of pattern for ( $i = 0; $i < $len2 ; $i ++) $hash_pat [ord( $pat [ $i ])]++; $start = 0; $start_index = -1; $min_len = PHP_INT_MAX; // start traversing the string $count = 0; // count of characters for ( $j = 0; $j < $len1 ; $j ++) { // count occurrence of characters // of string $hash_str [ord( $str [ $j ])]++; // If string's char matches with // pattern's char then increment count if ( $hash_str [ord( $str [ $j ])] <= $hash_pat [ord( $str [ $j ])]) $count ++; // if all the characters are matched if ( $count == $len2 ) { // Try to minimize the window i.e., // check if any character is occurring // more no. of times than its occurrence // in pattern, if yes then remove it from // starting and also remove the useless // characters. while ( $hash_str [ord( $str [ $start ])] > $hash_pat [ord( $str [ $start ])] || $hash_pat [ord( $str [ $start ])] == 0) { if ( $hash_str [ord( $str [ $start ])] > $hash_pat [ord( $str [ $start ])]) $hash_str [ord( $str [ $start ])]--; $start ++; } // update window size $len_window = $j - $start + 1; if ( $min_len > $len_window ) { $min_len = $len_window ; $start_index = $start ; } } } // If no window found if ( $start_index == -1) { echo "No such window exists" ; return "" ; } // Return substring starting from // start_index and length min_len return substr ( $str , $start_index , $min_len ); } // Driver code $str = "this is a test string" ; $pat = "tist" ; echo findSubString( $str , $pat ); // This code is contributed by // rathbhupendra ?> |
Python3
# Python3 program to find the smallest window # containing all characters of a pattern. no_of_chars = 256 # Function to find smallest window # containing all characters of 'pat' def findSubString(string, pat): len1 = len (string) len2 = len (pat) # Check if string's length is # less than pattern's # length. If yes then no such # window can exist if len1 < len2: print ( "No such window exists" ) return "" hash_pat = [ 0 ] * no_of_chars hash_str = [ 0 ] * no_of_chars # Store occurrence ofs characters of pattern for i in range ( 0 , len2): hash_pat[ ord (pat[i])] + = 1 start, start_index, min_len = 0 , - 1 , float ( 'inf' ) # Start traversing the string count = 0 # count of characters for j in range ( 0 , len1): # count occurrence of characters of string hash_str[ ord (string[j])] + = 1 # If string's char matches with # pattern's char then increment count if (hash_str[ ord (string[j])] < = hash_pat[ ord (string[j])]): count + = 1 # if all the characters are matched if count = = len2: # Try to minimize the window while (hash_str[ ord (string[start])] > hash_pat[ ord (string[start])] or hash_pat[ ord (string[start])] = = 0 ): if (hash_str[ ord (string[start])] > hash_pat[ ord (string[start])]): hash_str[ ord (string[start])] - = 1 start + = 1 # update window size len_window = j - start + 1 if min_len > len_window: min_len = len_window start_index = start # If no window found if start_index = = - 1 : print ( "No such window exists" ) return "" # Return substring starting from # start_index and length min_len return string[start_index: start_index + min_len] # Driver code if __name__ = = "__main__" : string = "this is a test string" pat = "tist" print (findSubString(string, pat)) # This code is contributed by Rituraj Jain |
Input: string = "this is a test string", pattern = "tist" Output: "t stri" Input: string = "w3wiki", pattern = "ork" Output: "ksfor"
Time Complexity: O(N), where N is the length of string.
Auxiliary Space: O(1)
Contact Us