Given a string S of size N consisting of the characters 0, 1 and 2, the task is to find the length of the smallest substring of string S that contains all the three characters 0, 1 and 2. If no such substring exists, then return -1.
Examples:
Input: S = “01212”
Output: 3
Explanation: The substring 012 is the smallest substring
that contains the characters 0, 1 and 2.Input: S = “12121”
Output: -1
Explanation: As the character 0 is not present in the
string S, therefore no substring containing
all the three characters 0, 1 and 2
exists. Hence, the answer is -1 in this case.
Approach: The idea of the approach is as mentioned below:
Use three pointers to store the indices of the elements 0, 1 and 2. When all the three elements are found, the difference distance between the maximum of them and the minimum of them is the minimum size window.
Keep updating the pointers whenever any of them is found again and calculate the size of the new window.
Follow the illustration below for a better understanding.
Illustration:
Consider S = “01212” and the three pointers to be zeroindex, oneindex and twoindex and set all of them to -1 initially.
When i = 0:
=> S[i] = ‘0’. zeroindex = 0, oneindex = -1, twoindex = -1
=> All of the values are not found. So no window is possibleWhen i = 1:
=> S[i] = ‘1’. zeroindex = 0, oneindex = 1, twoindex = -1
=> All of the values are not found. So no window is possibleWhen i = 2:
=> S[i] = ‘2’. zeroindex = 0, oneindex = 1, twoindex = 2
=> All of the values are found.
=> Maximum is twoindex = 2. Minimum is zeroindex = 0.
=> So window size = (2 – 0 + 1) = 3.
=> Minimum window size = 3When i = 3:
=> S[i] = ‘1’. zeroindex = 0, oneindex = 3, twoindex = 2
=> All of the values are found.
=> Maximum is oneindex = 3. Minimum is zeroindex = 0.
=> So window size = (3 – 0 + 1) = 4.
=> Minimum window size = min (3, 4) = 3When i = 4:
=> S[i] = ‘2’. zeroindex = 0, oneindex = 3, twoindex = 4
=> All of the values are found.
=> Maximum is twoindex = 4. Minimum is zeroindex = 0.
=> So window size = (4 – 0 + 1) = 5.
=> Minimum window size = min(3, 5) = 3So the size of the smallest window is 3
Follow the below steps to solve the problem:
- Take three variable zero, one and two to check if 0, 1 and 2 are found in the window or not.
- Take three variables zeroindex, oneindex and twoindex which will store indexes of 0, 1 and 2 when we encounter them.
- Run the for loop for the whole length of String:
- Update the indices of the values encountered.
- Update the length of the window, if three of them are found.
- Length will be the difference between the maximum and the minimum of the indexes of 0, 1 and 2.
- And if all three values i.e., 0, 1, 2 are not found after the traversal is over then in that case return ‘-1’.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the smallest substringint smallestSubstring(string S){ int res = INT_MAX; // To check 0, 1 and 2 bool zero = false, one = false, two = false; // To store indexes of 0, 1 and 2 int zeroindex, oneindex, twoindex; for (int i = 0; i < S.length(); i++) { if (S[i] == '0') { zero = true; zeroindex = i; } else if (S[i] == '1') { one = true; oneindex = i; } else if (S[i] == '2') { two = true; twoindex = i; } // Calculating length if (zero and one and two) res = min(res, max({ zeroindex, oneindex, twoindex }) - min({ zeroindex, oneindex, twoindex })); } // In case if there is no substring that contains 0,1 and 2 if (res == INT_MAX) return -1; return res + 1;}// Driver Codeint main(){ string S = "01212"; // Function call cout << smallestSubstring(S); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program for above approach#include <limits.h> // to use INT_MAX#include <stdbool.h> //to use bool variable#include <stdio.h>// function to calculate max of two numbersint min_two(int a, int b){ if (a <= b) return a; else return b;}// function to calculate max of three numbersint max_three(int a, int b, int c){ if (a >= b && a >= c) return a; else if (b > a && b >= c) return b; else if (c > a && c > b) return c;}// function to calculate min of three numbersint min_three(int a, int b, int c){ if (a <= b && a <= c) return a; else if (b < a && b <= c) return b; else if (c < a && c < b) return c;}// Function to find the length of// the smallest substringint smallestSubstring(char S[], int n){ int res = INT_MAX; // To check 0, 1 and 2 bool zero = 0, one = 0, two = 0; // To store indexes of 0, 1 and 2 int zeroindex, oneindex, twoindex; for (int i = 0; i < n; i++) { if (S[i] == '0') { zero = true; zeroindex = i; } else if (S[i] == '1') { one = true; oneindex = i; } else if (S[i] == '2') { two = true; twoindex = i; } // Calculating length if (zero && one && two) res = min_two( res, max_three(zeroindex, oneindex, twoindex) - min_three(zeroindex, oneindex, twoindex)); } // In case if there is no substring that contains 0,1 and 2 if (res == INT_MAX) return -1; return res + 1;}// Driver Codeint main(){ int n = 5; // size of string char S[] = "01212"; int ans = smallestSubstring(S, n); // Function call printf("%d", ans); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program for above approachimport java.util.*;class GFG { // Function to find the length of the smallest substring public static int smallestSubstring(String S) { int res = Integer.MAX_VALUE; // To check 0, 1 and 2 boolean zero = false, one = false, two = false; // To store indexes of 0, 1 and 2 int zeroindex = 0, oneindex = 0, twoindex = 0; for (int i = 0; i < S.length(); i++) { if (S.charAt(i) == '0') { zero = true; zeroindex = i; } else if (S.charAt(i) == '1') { one = true; oneindex = i; } else if (S.charAt(i) == '2') { two = true; twoindex = i; } // Calculating length if (zero && one && two) res = Math.min( res, Math.max(zeroindex,Math.max(oneindex, twoindex)) - Math.min( zeroindex,Math.min(oneindex, twoindex))); } // In case if there is no substring that contains 0,1 and 2 if (res == Integer.MAX_VALUE) return -1; return res + 1; } // Driver Code public static void main(String[] args) { String S = "01212"; // Function call System.out.print(smallestSubstring(S)); }}// This code is contributed by Aditya Kumar (adityakumar129) |
Python3
# Python code for the above approach# Function to find the length of the smallest substringdef smallestSubstring(S): res = 999999 # To check 0, 1 and 2 zero = 0 one = 0 two = 0 # To store indexes of 0, 1 and 2 zeroindex = 0 oneindex = 0 twoindex = 0 for i in range(len(S)): if (S[i] == '0'): zero = 1 zeroindex = i elif (S[i] == '1'): one = 1 oneindex = i elif (S[i] == '2'): two = 1 twoindex = i # Calculating length if (zero and one and two): res = min(res, max([zeroindex, oneindex, twoindex]) - min([zeroindex, oneindex, twoindex])) # In case if there is no substring that contains 0,1 and 2 if (res == 999999): return -1 return res + 1# Driver CodeS = "01212"# Function callprint(smallestSubstring(S))# This code is contributed by Aditya Kumar (adityakumar129) |
C#
// C# program for above approachusing System;public class GFG { // Function to find the length of the smallest substring static int smallestSubstring(string S) { int res = Int32.MaxValue; // To check 0, 1 and 2 bool zero = false, one = false, two = false; // To store indexes of 0, 1 and 2 int zeroindex = 0, oneindex = 0, twoindex = 0; for (int i = 0; i < S.Length; i++) { if (S[i] == '0') { zero = true; zeroindex = i; } else if (S[i] == '1') { one = true; oneindex = i; } else if (S[i] == '2') { two = true; twoindex = i; } // Calculating length if (zero && one && two) res = Math.Min(res, Math.Max( zeroindex, Math.Max(oneindex, twoindex)) - Math.Min( zeroindex, Math.Min(oneindex, twoindex))); } // In case if there is no substring that contains 0,1 and 2 if (res == Int32.MaxValue) return -1; return res + 1; } // Driver Code static public void Main() { string S = "01212"; // Function call Console.Write(smallestSubstring(S)); }}// This code is contributed by Aditya Kumar (adityakumar129) |
Javascript
<script> // JavaScript program for above approach const INT_MAX = 2147483647; // Function to find the length of // the smallest substring const smallestSubstring = (S) => { let res = INT_MAX; // To check 0, 1 and 2 let zero = false, one = false, two = false; // To store indexes of 0, 1 and 2 let zeroindex, oneindex, twoindex; for (let i = 0; i < S.length; i++) { if (S[i] == '0') { zero = true; zeroindex = i; } else if (S[i] == '1') { one = true; oneindex = i; } else if (S[i] == '2') { two = true; twoindex = i; } // Calculating length if (zero && one && two) res = Math.min(res, Math.max(...[zeroindex, oneindex, twoindex]) - Math.min(...[zeroindex, oneindex, twoindex])); } // In case if there is no substring that contains 0,1 and 2 if (res == INT_MAX) return -1; return res + 1; } // Driver Code let S = "01212"; // Function call document.write(smallestSubstring(S)); // This code is contributed by Aditya Kumar (adityakumar129)</script> |
Output
3
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Another Approach: using a sliding window
- Initialize three pointers i, j, and k to 0.
- Initialize a variable min_len to the maximum integer value.
- Initialize an array freq[] to 0 of size 3 to keep track of the frequency of each character in the current window.
Traverse the string S using the pointer k:
a. Increment the frequency of the character S[k] in the freq[] array.
b. If freq[S[k]-‘0’] equals 1 (i.e., this character was not in the window before), increment a counter cnt.
c. If cnt equals 3, then we have found a window containing all three characters. Now, we can try to shrink the window from the left by incrementing i - until the frequency of any character becomes zero. While doing this, we also update the freq[] array and decrement the cnt if the frequency of any character becomes zero.
d. After shrinking the window, update the value of min_len if the current window size is smaller than min_len. - Return min_len if it is less than the maximum integer value, else return -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int smallestSubstring(string S) { int n = S.length(), i = 0, j = 0, k = 0, cnt = 0, min_len = INT_MAX; int freq[3] = {0}; while (k < n) { freq[S[k]-'0']++; if (freq[S[k]-'0'] == 1) cnt++; if (cnt == 3) { while (freq[S[i]-'0'] > 1) { freq[S[i]-'0']--; i++; } min_len = min(min_len, k-i+1); freq[S[i]-'0']--; i++; cnt--; } k++; } return (min_len == INT_MAX) ? -1 : min_len;}int main() { string S = "01212"; cout << smallestSubstring(S) << endl; return 0;} |
Java
import java.util.Arrays;public class Main { public static int smallestSubstring(String S) { int n = S.length(), i = 0, j = 0, k = 0, cnt = 0, min_len = Integer.MAX_VALUE; int[] freq = new int[3]; Arrays.fill(freq, 0); while (k < n) { freq[S.charAt(k)-'0']++; if (freq[S.charAt(k)-'0'] == 1) cnt++; if (cnt == 3) { while (freq[S.charAt(i)-'0'] > 1) { freq[S.charAt(i)-'0']--; i++; } min_len = Math.min(min_len, k-i+1); freq[S.charAt(i)-'0']--; i++; cnt--; } k++; } return (min_len == Integer.MAX_VALUE) ? -1 : min_len; } public static void main(String[] args) { String S = "01212"; System.out.println(smallestSubstring(S)); }}// This code is contributed by Prajwal Kandekar |
Python3
# Python program to find the smallest # substring containing all unique charactersdef smallestSubstring(S): # Initialize variables n, i, j, k, cnt, min_len = len(S), 0, 0, 0, 0, float("inf") # Frequency array freq = [0] * 3 while k < n: freq[int(S[k])] += 1 if freq[int(S[k])] == 1: cnt += 1 if cnt == 3: while freq[int(S[i])] > 1: freq[int(S[i])] -= 1 i += 1 min_len = min(min_len, k-i+1) freq[int(S[i])] -= 1 i += 1 cnt -= 1 k += 1 # Return minimum length substring or -1 if no such substring exists return -1 if min_len == float("inf") else min_len# Driver codeS = "01212"# Function callprint(smallestSubstring(S))# This code is contributed by phasing17 |
C#
using System;public class MainClass { public static int SmallestSubstring(string s) { int n = s.Length, i = 0, j = 0, k = 0, cnt = 0, min_len = int.MaxValue; int[] freq = new int[3]; Array.Fill(freq, 0); while (k < n) { freq[s[k]-'0']++; if (freq[s[k]-'0'] == 1) cnt++; if (cnt == 3) { while (freq[s[i]-'0'] > 1) { freq[s[i]-'0']--; i++; } min_len = Math.Min(min_len, k-i+1); freq[s[i]-'0']--; i++; cnt--; } k++; } return (min_len == int.MaxValue) ? -1 : min_len; } public static void Main(string[] args) { string s = "01212"; Console.WriteLine(SmallestSubstring(s)); }} |
Javascript
function smallestSubstring(S) { // Initialize variables let n = S.length, i = 0, j = 0, k = 0, cnt = 0, min_len = Infinity; // Frequency array let freq = [0, 0, 0]; while (k < n) { freq[parseInt(S[k])] += 1; if (freq[parseInt(S[k])] == 1) { cnt += 1; } if (cnt == 3) { while (freq[parseInt(S[i])] > 1) { freq[parseInt(S[i])] -= 1; i += 1; } min_len = Math.min(min_len, k - i + 1); freq[parseInt(S[i])] -= 1; i += 1; cnt -= 1; } k += 1; } // Return minimum length substring or -1 if no such substring exists return min_len == Infinity ? -1 : min_len;}// Driver codelet S = "01212";// Function callconsole.log(smallestSubstring(S)); |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
