The objective is to identify the smallest substring in S that contains every character of P, including duplicates, given two strings S (length m) and P (length n). Return “-1” if there isn’t a substring of that kind. Return the substring with the least starting index if more than one of the same length is found.
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.
Table of Content
- [Naive Approach] By Generating all the Substrings – O(N^3) Time and O(N) Space
- [Better Approach] By using Binary Search on Answer – O(N*logN) Time and O(1) Space
- [Expected Approach] By using Hashing and Two pointers – O(N) Time and O(1) Space
[Naive Method] O(N^3) by Generating Every Substring O(N) Space and Time:
Creating every feasible substring from the provided string S and determining if each substring contains every character in the string P is the fundamental principle behind solving this challenge. A helper function that counts the frequency of each character in P and compares it to the frequency of the selected substring can accomplish this checking. The shortest substring is updated in accordance with the current minimum length if a substring contains every character of the P. Until every substring has been examined, the procedure is repeated.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check if the substring contains all
// characters of the pattern
bool containsAllCharacters(string& s, 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 : 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
string findSmallestSubstring(string& s, string& p)
{
int m = s.length();
int n = p.length();
string smallestSubstring = "";
int minLen = INT_MAX;
// Generate all substrings of the given string
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
string substr = s.substr(i, j - i + 1);
// Check if the substring contains all
// characters of the pattern
if (containsAllCharacters(substr, p)) {
int currLen = substr.length();
// Update the smallestSubstring if the
// current substring is smaller
if (currLen < minLen) {
minLen = currLen;
smallestSubstring = substr;
}
}
}
}
return smallestSubstring;
}
int main() {
string s = "timetopractice";
string p = "toc";
string result = findSmallestSubstring(s, p);
if (!result.empty()) {
cout << result << endl;
} else {
cout << -1 << endl;
}
return 0;
}
C
#include <stdio.h>
#include <string.h>
#include <limits.h>
// Function to check if the substring contains all
// characters of the pattern
int containsAllCharacters(char* s, char* p)
{
int count[256] = { 0 };
// Count the frequency of each character
// in the pattern
for (int i = 0; p[i] != '\0'; i++)
count[(unsigned char)p[i]]++;
// For each character in the substring,
// decrement its count
for (int i = 0; s[i] != '\0'; i++) {
if (count[(unsigned char)s[i]] > 0)
count[(unsigned char)s[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 0;
}
return 1;
}
// Function to find the smallest substring containing all
// characters of the pattern
void findSmallestSubstring(char* s, char* p, char* result)
{
int m = strlen(s);
int n = strlen(p);
int minLen = INT_MAX;
result[0] = '\0';
// Generate all substrings of the given string
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
char substr[100];
strncpy(substr, s + i, j - i + 1);
substr[j - i + 1] = '\0';
// Check if the substring contains all
// characters of the pattern
if (containsAllCharacters(substr, p)) {
int currLen = strlen(substr);
// Update the smallestSubstring if the
// current substring is smaller
if (currLen < minLen) {
minLen = currLen;
strcpy(result, substr);
}
}
}
}
}
int main() {
char s[] = "timetopractice";
char p[] = "toc";
char result[100];
findSmallestSubstring(s, p, result);
if (strlen(result) > 0) {
printf("%s\n", result);
} else {
printf("-1\n");
}
return 0;
}Java
import java.util.Arrays;
public class GFG {
// Function to check if the substring contains all
// characters of the pattern
public static boolean containsAllCharacters(String s,
String p)
{
int[] count = new int[256];
Arrays.fill(count, 0);
// Count the frequency of each character in the
// pattern
for (char ch : p.toCharArray())
count[ch]++;
// For each character in the substring, decrement
// its count
for (char ch : s.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 c : count) {
if (c > 0)
return false;
}
return true;
}
// Function to find the smallest substring containing
// all characters of the pattern
public static String findSmallestSubstring(String s,
String p)
{
int m = s.length();
int n = p.length();
String smallestSubstring = "";
int minLen = Integer.MAX_VALUE;
// Generate all substrings of the given string
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
String substr = s.substring(i, j + 1);
// Check if the substring contains all
// characters of the pattern
if (containsAllCharacters(substr, p)) {
int currLen = substr.length();
// Update the smallestSubstring if the
// current substring is smaller
if (currLen < minLen) {
minLen = currLen;
smallestSubstring = substr;
}
}
}
}
return smallestSubstring;
}
public static void main(String[] args)
{
String s = "timetopractice";
String p = "toc";
String result = findSmallestSubstring(s, p);
if (!result.isEmpty()) {
System.out.println(result);
}
else {
System.out.println(-1);
}
}
}Python
def contains_all_characters(s, p):
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,
# substring contains all characters of the pattern
return all(c == 0 for c in count)
def find_smallest_substring(s, p):
m = len(s)
n = len(p)
smallest_substring = ""
min_len = float('inf')
# Generate all substrings of the given string
for i in range(m):
for j in range(i, m):
substr = s[i:j + 1]
# Check if the substring contains all
# characters of the pattern
if contains_all_characters(substr, p):
curr_len = len(substr)
# Update the smallest_substring if the
# current substring is smaller
if curr_len < min_len:
min_len = curr_len
smallest_substring = substr
return smallest_substring
if __name__ == "__main__":
s = "timetopractice"
p = "toc"
result = find_smallest_substring(s, p)
if result:
print(result)
else:
print(-1)JS
// Function to check if the substring contains all
// characters of the pattern
function containsAllCharacters(s, p) {
let 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
return count.every(c => c === 0);
}
// Function to find the smallest substring containing all
// characters of the pattern
function findSmallestSubstring(s, p) {
let m = s.length;
let n = p.length;
let smallestSubstring = "";
let minLen = Number.MAX_SAFE_INTEGER;
// Generate all substrings of the given string
for (let i = 0; i < m; i++) {
for (let j = i; j < m; j++) {
let substr = s.slice(i, j + 1);
// Check if the substring contains all
// characters of the pattern
if (containsAllCharacters(substr, p)) {
let currLen = substr.length;
// Update the smallestSubstring if the
// current substring is smaller
if (currLen < minLen) {
minLen = currLen;
smallestSubstring = substr;
}
}
}
}
return smallestSubstring;
}
let s = "timetopractice";
let p = "toc";
let result = findSmallestSubstring(s, p);
if (result) {
console.log(result);
} else {
console.log(-1);
}Output
toprac
Time Complexity: O(N3)
Auxiliary Space: O(N) to create substrings.