Given a string str, find the smallest window length that contains all the characters of the given string at least one time.
Examples:
Input: str = "aabcbcdbca"
Output: 4
Explanation: Sub-string -> "dbca"Input: str = "aaab"
Output: 2
Explanation: Sub-string -> "ab"
Try it on GfG Practice
Table of Content
[Naive Approach] - Generating All Substrings - O(n ^ 2) Time and O(1) Space
- Use a count array to identify all the unique characters in the string.
- Generate substrings using two pointers and track characters using a visited array.
- Check whether the current substring contains all distinct characters.
- If it does, update the minimum length of the substring found so far.
#include <iostream>
using namespace std;
int findSubString(string &str) {
int n = str.size();
int ans = n;
// to store all distinct characters
vector<bool> visited(26, false);
for (int i = 0; i < n; i++) {
visited[str[i]-'a'] = true;
}
for(int i = 0; i < n; i++) {
vector<bool> cur(26, false);
for(int j = i; j < n; j++) {
cur[str[j]-'a'] = true;
// if all characters are present
if(cur == visited) {
ans = min(ans, j - i + 1);
break;
}
}
}
return ans;
}
int main() {
string str = "aabcbcdbca";
cout << findSubString(str);
return 0;
}
import java.util.Arrays;
class GfG {
public static int findSubString(String str) {
int n = str.length();
int ans = n;
// to store all distinct characters
boolean[] visited = new boolean[26];
for (int i = 0; i < n; i++) {
visited[str.charAt(i) - 'a'] = true;
}
for (int i = 0; i < n; i++) {
boolean[] cur = new boolean[26];
for (int j = i; j < n; j++) {
cur[str.charAt(j) - 'a'] = true;
// if all characters are present
if (Arrays.equals(cur, visited)) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans;
}
public static void main(String[] args) {
String str = "aabcbcdbca";
System.out.print(findSubString(str));
}
}
def findSubString(str):
n = len(str)
ans = n
# to store all distinct characters
visited = [False] * 26
for i in range(n):
visited[ord(str[i]) - ord('a')] = True
for i in range(n):
cur = [False] * 26
for j in range(i, n):
cur[ord(str[j]) - ord('a')] = True
# if all characters are present
if cur == visited:
ans = min(ans, j - i + 1)
break
return ans
if __name__ == "__main__":
str = "aabcbcdbca"
print(findSubString(str))
using System;
using System.Linq;
class GfG {
public static int findSubString(string str) {
int n = str.Length;
int ans = n;
// to store all distinct characters
bool[] visited = new bool[26];
for (int i = 0; i < n; i++) {
visited[str[i] - 'a'] = true;
}
for (int i = 0; i < n; i++) {
bool[] cur = new bool[26];
for (int j = i; j < n; j++) {
cur[str[j] - 'a'] = true;
// if all characters are present
if (cur.SequenceEqual(visited)) {
ans = Math.Min(ans, j - i + 1);
break;
}
}
}
return ans;
}
static void Main() {
string str = "aabcbcdbca";
Console.Write(findSubString(str));
}
}
function findSubString(str) {
let n = str.length;
let ans = n;
// to store all distinct characters
let visited = new Array(26).fill(false);
for (let i = 0; i < n; i++) {
visited[str.charCodeAt(i) - 97] = true;
}
for (let i = 0; i < n; i++) {
let cur = new Array(26).fill(false);
for (let j = i; j < n; j++) {
cur[str.charCodeAt(j) - 97] = true;
// if all characters are present
if (JSON.stringify(cur) === JSON.stringify(visited)) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans;
}
let str = "aabcbcdbca";
console.log(findSubString(str));
Output
4
[Expected Approach] - Using Sliding Window - O(n) Time and O(1) Space
- Count total distinct characters in the string using a visited array.
- Use a sliding window with two pointers (start and i) to expand the window and include characters.
- Track character frequencies in the window using cur[] and update cnt when a new distinct character appears.
- When the window contains all distinct characters, shrink it from the left and update the minimum window length.
#include <iostream>
using namespace std;
int findSubString(string str) {
int n = str.size();
// to store all distinct characters
vector<bool> visited(26, false);
int distinct = 0;
for (int i = 0; i < n; i++) {
if (visited[str[i] - 'a'] == false) {
visited[str[i] - 'a'] = true;
distinct++;
}
}
// to store the visited of characters
// in the current window
vector<int> cur(26, 0);
int cnt = 0;
int ans = n;
int start = 0;
for(int i = 0; i < n; i++) {
// Count characters in the current
// window
cur[str[i] - 'a']++;
if(cur[str[i] - 'a'] == 1) {
cnt++;
}
// If the count becomes same as overall
while(cnt == distinct) {
ans = min(ans, i - start + 1);
// Remove characters from left
cur[str[start] - 'a']--;
if(cur[str[start] - 'a'] == 0) {
cnt--;
}
start++;
}
}
return ans;
}
int main() {
string str = "aabcbcdbca";
cout << findSubString(str);
return 0;
}
import java.util.Arrays;
class GfG {
public static int findSubString(String str) {
int n = str.length();
// to store all distinct characters
boolean[] visited = new boolean[26];
int distinct = 0;
for (int i = 0; i < n; i++) {
if (visited[str.charAt(i) - 'a'] == false) {
visited[str.charAt(i) - 'a'] = true;
distinct++;
}
}
// to store the visited of characters
// in the current window
int[] cur = new int[26];
int cnt = 0;
int ans = n;
int start = 0;
for (int i = 0; i < n; i++) {
cur[str.charAt(i) - 'a']++;
if (cur[str.charAt(i) - 'a'] == 1) {
cnt++;
}
while (cnt == distinct) {
ans = Math.min(ans, i - start + 1);
cur[str.charAt(start) - 'a']--;
if (cur[str.charAt(start) - 'a'] == 0) {
cnt--;
}
start++;
}
}
return ans;
}
public static void main(String[] args) {
String str = "aabcbcdbca";
System.out.print(findSubString(str));
}
}
def findSubString(str):
n = len(str)
# to store all distinct characters
visited = [False] * 26
distinct = 0
for i in range(n):
if visited[ord(str[i]) - ord('a')] == False:
visited[ord(str[i]) - ord('a')] = True
distinct += 1
# to store the visited of characters
# in the current window
cur = [0] * 26
cnt = 0
ans = n
start = 0
for i in range(n):
cur[ord(str[i]) - ord('a')] += 1
if cur[ord(str[i]) - ord('a')] == 1:
cnt += 1
while cnt == distinct:
ans = min(ans, i - start + 1)
cur[ord(str[start]) - ord('a')] -= 1
if cur[ord(str[start]) - ord('a')] == 0:
cnt -= 1
start += 1
return ans
if __name__ == "__main__":
str = "aabcbcdbca"
print(findSubString(str))
using System;
class GfG {
public static int findSubString(string str) {
int n = str.Length;
// to store all distinct characters
bool[] visited = new bool[26];
int distinct = 0;
for (int i = 0; i < n; i++) {
if (visited[str[i] - 'a'] == false) {
visited[str[i] - 'a'] = true;
distinct++;
}
}
// to store the visited of characters
// in the current window
int[] cur = new int[26];
int cnt = 0;
int ans = n;
int start = 0;
for (int i = 0; i < n; i++) {
cur[str[i] - 'a']++;
if (cur[str[i] - 'a'] == 1) {
cnt++;
}
while (cnt == distinct) {
ans = Math.Min(ans, i - start + 1);
cur[str[start] - 'a']--;
if (cur[str[start] - 'a'] == 0) {
cnt--;
}
start++;
}
}
return ans;
}
static void Main() {
string str = "aabcbcdbca";
Console.Write(findSubString(str));
}
}
function findSubString(str) {
let n = str.length;
// to store all distinct characters
let visited = new Array(26).fill(false);
let distinct = 0;
for (let i = 0; i < n; i++) {
if (visited[str.charCodeAt(i) - 97] == false) {
visited[str.charCodeAt(i) - 97] = true;
distinct++;
}
}
// to store the visited of characters
// in the current window
let cur = new Array(26).fill(0);
let cnt = 0;
let ans = n;
let start = 0;
for (let i = 0; i < n; i++) {
cur[str.charCodeAt(i) - 97]++;
if (cur[str.charCodeAt(i) - 97] == 1) {
cnt++;
}
while (cnt == distinct) {
ans = Math.min(ans, i - start + 1);
cur[str.charCodeAt(start) - 97]--;
if (cur[str.charCodeAt(start) - 97] == 0) {
cnt--;
}
start++;
}
}
return ans;
}
// driver code
let str = "aabcbcdbca";
console.log(findSubString(str));
Output
4
Related Article: