Problem Statement:
You are given a string ‘s’. You need to find the smallest window length that contains all the characters of the string.
Example
Input : "aaab" Output : 2 Sub string : "ab"
Solution
We can solve this problem using Sliding Window Approach.
For that we need 2 pointers start and end.
Start is used to shrink the elements from left, end is used to add the elements from right,.
Example:
a a a b Pass 1: a a a b ^ ^ | | S E Now we move the end pointer Pass 2: a a a b ^ ^ | | S E Now we shrink the Start pointer to remove the duplicates Pass 3: a a a b ^ ^ | | S E Now move the End pointer Pass 4: a a a b ^ ^ | | S E Now shrink the Start pointer to remove the duplicates. Pass 5: a a a b ^ ^ | | S E We got the answer. we follow below steps for the solution: 1. First calculate the distinct characters in the string. 2. Take 2 pointers start and end.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <queue> #include <vector> #include <stack> using namespace std; const int MAX_CHARS = 256; string get_sub_string(string str) { int n = str.length(); // get the count all distinct characters. int dist_count = 0; bool visited[MAX_CHARS] = { false }; for (int i = 0; i < n; i++) { if (visited[str[i]] == false) { visited[str[i]] = true; dist_count++; } } int start = 0; int start_index = -1; int min_len = INT_MAX; int count = 0; int curr_count[MAX_CHARS] = { 0 }; for (int j = 0; j < n; j++) { curr_count[str[j]]++; if (curr_count[str[j]] == 1) count++; if (count == dist_count) { while (curr_count[str[start]] > 1) { if (curr_count[str[start]] > 1) curr_count[str[start]]--; start++; } int len_window = j - start + 1; if (min_len > len_window) { min_len = len_window; start_index = start; } } } return str.substr(start_index, min_len); } int main() { string str = "aaabbcddabc"; cout << "Smallest window is " << get_sub_string(str); return 0; }
Output:
Smallest window is dabc