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.
Try it on GfG Practice
Table of Content
[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.
#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");
}
Output
toprac
[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.
#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 minWindow(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 << minWindow(s, p) << endl;
return 0;
}
import java.util.HashMap;
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 minWindow(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 "";
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(minWindow(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 minWindow(s, p):
m = len(s)
n = len(p)
# If s is smaller than p, it's impossible
if m < n:
return ""
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(minWindow(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 minWindow(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 "";
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(minWindow(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 minWindow(s, p){
const m = s.length;
const n = p.length;
// If s is smaller than p, it's impossible
if (m < n)
return "";
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(minWindow(s, p));
Output
toprac
[Expected Approach] Using Window Sliding - O(n) Time and O(1) Space:
The idea is to use Window Sliding (
startandj) to maintain a sliding window over stringS, while tracking character frequencies with two count arrays.
Steps:
- 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.
- A count array to store the frequency of characters in
- Expand the Window:
- Move the
jpointer throughS, updating the window's character counts. - When all characters of
Pare present in the window, a valid window is found.
- Move the
- Shrink the Window before updating result
- Move the
startpointer right to minimize the window while ensuring all characters fromPremain in the window. - Track the smallest window during this process.
- Move the
- Return Result:
- If a valid window is found, return the smallest substring. If no valid window exists, return
"-1".
- If a valid window is found, return the smallest substring. If no valid window exists, return
Illustration:
#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;
string minWindow(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 = minWindow(s, p);
cout << res;
return 0;
}
class GfG {
public static String minWindow(String s, String p) {
int len1 = s.length();
int len2 = p.length();
if (len1 < len2)
return "";
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 = minWindow(s, p);
System.out.println(res);
}
}
def minWindow(s, p):
len1 = len(s)
len2 = len(p)
if len1 < len2:
return ""
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 = minWindow(s, p)
print(res)
using System;
using System.Collections.Generic;
class GfG {
public static string minWindow(string s, string p) {
int len1 = s.Length;
int len2 = p.Length;
if (len1 < len2)
return "";
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 = minWindow(s, p);
Console.WriteLine(res);
}
}
function minWindow(s, p) {
let len1 = s.length;
let len2 = p.length;
if (len1 < len2) {
return "";
}
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 = minWindow(s, p);
console.log(result);
Output
toprac