C++ Smallest window with all characters in string














































C++ Smallest window with all characters in string



Smallest window that contains all characters of string itself


Given a string, find the smallest window length with all distinct characters of the given string. For eg. str = aabcbcdbca, then the result would be 4 as of the smallest window will be  dbca  .

Examples:

Input: aabcbcdbca
Output: dbca
Explanation:
Possible substrings= {aabcbcd, abcbcd,
bcdbca, dbca....}
Of the set of possible substrings 'dbca'
is the shortest substring having all the
distinct characters of given string.

Input: aaab
Output: ab
Explanation:
Possible substrings={aaab, aab, ab}
Of the set of possible substrings 'ab'
is the shortest substring having all
the distinct characters of given string.


Solution: Above problem states that we have to find the smallest window that contains all the distinct characters of the given string even if the smallest string contains repeating elements.
For example, in  aabcbcdb , the smallest string that contains all the characters is  abcbcd.

Method 1: This is the Brute Force method of solving the problem using HashMap.

  • Approach : For solving the problem we first have to find out all the distinct characters present in the string. This can be done using a HashMap. The next thing is to generate all the possible substrings. This follows by checking whether a substring generated has all the required characters(stored in the hash_map) or not. If yes, then compare its length with the minimum substring length which follows the above constraints, found till now.

  • HashMap: HashMap is a part of Java's collection since Java 1.2. It provides the basic implementation of the Map interface of Java. It stores the data in (Key, Value) pairs. To access a value one must know its key. HashMap is known as HashMap because it uses a technique called Hashing. Hashing is a technique of converting a large String to small String that represents the same String. A shorter value helps in indexing and faster searches. HashSet also uses HashMap internally. It internally uses a link list to store key-value pairs already explained in HashSet in detail and further articles.
  • Algorithm :
    1. Store all distinct characters of the given string in a hash_map.
    2. Take a variable count and initialize it with value 0.
    3. Generate the substrings using two pointers.
    4. Now check whether generated substring is valid or not-:
      1. As soon we find that the character of the substring generated has not been encountered before, increment count by 1.
      2. We can use a visited array of max_chars size to find whether the current character has been encountered before or not.
      3. If count is equal to equal to size of hash_map the substring generated is valid
      4. If it is a valid substring, compare it with the minimum length substring already generated.
  • Pseudo Code:
    maphash_map;
    for ( i=0 to str.length())
    hash_map[str[i]]++;//finding all distinct charaters of string
    minimum_size=INT_MAX
    Distinct_chars=hash_map.size()
    for(i=0 to str.length())
    count=0;
    sub_str="";
    visited[256]={0};
    for(j=i to n)
    sub_str+=str[j]
    if(visited[str[j]]==0)
    count++
    visited[str[j]]=1;
    if(count==Distinct_chars)
    end loop

    if(sub_str.length()<minimum_size&&
    count==Distinct_chars)
    ans=sub_str;

    return ans
  • Implementation:
    fil
    ter_none
    edit

    play_arrow

    brightness_4

    // C++ program to find the smallest
    // window containing all characters
    // of a pattern.
    #include <bits/stdc++.h>
    using namespace std;
    const int MAX_CHARS = 256;
    // Function to find smallest window containing
    // all distinct characters
    string findSubString(string str)
    {
    int n = str.length();
    // Count all distinct characters.
    int dist_count = 0;
    unordered_map<int, int> hash_map;
    for (int i = 0; i < n; i++) {
    hash_map[str[i]]++;
    }
    dist_count = hash_map.size();
    int size = INT_MAX;
    string res;
    // Now follow the algorithm discussed in below
    for (int i = 0; i < n; i++) {
    int count = 0;
    int visited[256] = { 0 };
    string sub_str = "";
    for (int j = i; j < n; j++) {
    if (visited[str[j]] == 0) {
    count++;
    visited[str[j]] = 1;
    }
    sub_str += str[j];
    if (count == dist_count)
    break;
    }
    if (sub_str.length() < size && count == dist_count)
    res = sub_str;
    }
    return res;
    }
    // Driver Code
    int main()
    {
    string str = "aabcbcdbca";
    cout << "Smallest window containing all distinct"
    " characters is: "
    << findSubString(str);
    return 0;
    }
    Output:
    Smallest window containing all 
    distinct characters is: dbca
  • Complexiy Analysis:
    • Time Complexity: O(N^2).
      This time is required to generate all possible sub-strings of a string of length N.
    • Space Complexity: O(N).
      As a hash_map has been used of size N.

Method 2: Here we have used Sliding Window technique to arrive at the solution. This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.

  • Approach: Basically a window of characters is maintained by using two pointers namely start and end. These start and end pointers can be used to shrink and increase the size of window respectively. Whenever the window contains all characters of given string, the window is shrinked from left side to remove extra characters and then its length is compared with the smallest window found so far.
    If in the present window, no more characters can be deleted then we start increasing the size of the window using the end until all the distinct characters present in the string are also there in the window. Finally, find the minimum size of each window.
  • Algorithm :
    1. Maintain an array (visited) of maximum possible characters (256 characters) and as soon as we find any in the string, mark that index in the array (this is to count all distinct characters in the string).
    2. Take two pointers start and end which will mark the start and end of window.
    3. Take a counter=0 which will be used to count distinct characters in the window.
    4. Now start reading the characters of the given string and if we come across a character which has not been visited yet increment the counter by 1.
    5. If the counter is equal to total number of distinct characters, Try to shrink the window.
    6. For shrinking the window -:
      1. If the frequency of character at start pointer is greater than 1 increment the pointer as it is redundant.
      2. Now compare the length of present window with the minimum window length.
  • Implementation:
    filter_none

    // C++ program to find the smallest
    // window containing all characters
    // of a pattern.
    #include <bits/stdc++.h>
    using namespace std;
    const int MAX_CHARS = 256;
    // Function to find smallest window containing
    // all distinct characters
    string findSubString(string str)
    {
    int n = str.length();
    // 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++;
    }
    }
    // Now follow the algorithm discussed in below
    // post. We basically maintain a window of characters
    // that contains all characters of given string.
    int start = 0, start_index = -1, min_len = INT_MAX;
    int count = 0;
    int curr_count[MAX_CHARS] = { 0 };
    for (int j = 0; j < n; j++) {
    // Count occurrence of characters of string
    curr_count[str[j]]++;
    // If any distinct character matched,
    // then increment count
    if (curr_count[str[j]] == 1)
    count++;
    // if all the characters are matched
    if (count == dist_count) {
    // Try to minimize the window i.e., check if
    // any character is occurring more no. of times
    // than its occurrence in pattern, if yes
    // then remove it from starting and also remove
    // the useless characters.
    while (curr_count[str[start]] > 1) {
    if (curr_count[str[start]] > 1)
    curr_count[str[start]]--;
    start++;
    }
    // Update window size
    int len_window = j - start + 1;
    if (min_len > len_window) {
    min_len = len_window;
    start_index = start;
    }
    }
    }
    // Return substring starting from start_index
    // and length min_len
    return str.substr(start_index, min_len);
    }
    // Driver code
    int main()
    {
    string str = "aabcbcdbca";
    cout << "Smallest window containing all distinct"
    " characters is: "
    << findSubString(str);
    return 0;
    }
    Output:
    Smallest window containing all 
    distinct characters is dbca
  • Complexiy Analysis:
    • Time Complexity: O(N).
      As the string is traversed using two pointers only once.
    • Space Complexity: O(N).
      As a hash_map is used of size N.

More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 285 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 121 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 200 0
C++ Smallest window with all characters in string 94 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 87 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 90 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 333 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 349 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2

Comments