Strings: Smallest distinct window

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