Click here to Skip to main content
15,031,145 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Find the smallest window in a string containing all characters of another string - GeeksforGeeks[^]

I can't wrap my head around this code. What does array inside an array mean? How can a character be an index to an array?

What I have tried:

// C++ program to find smallest window containing 
// all characters of a pattern. 
#include<bits/stdc++.h> 
using namespace std; 

const int no_of_chars = 256; 

// Function to find smallest window containing 
// all characters of 'pat' 
string findSubString(string str, string pat) 
{ 
	int len1 = str.length(); 
	int len2 = pat.length(); 

	// check if string's length is less than pattern's 
	// length. If yes then no such window can exist 
	if (len1 < len2) 
	{ 
		cout << "No such window exists"; 
		return ""; 
	} 

	int hash_pat[no_of_chars] = {0}; 
	int hash_str[no_of_chars] = {0}; 

	// store occurrence ofs characters of pattern 
	for (int i = 0; i < len2; i++) 
		hash_pat[pat[i]]++; 

	int start = 0, start_index = -1, min_len = INT_MAX; 

	// start traversing the string 
	int count = 0; // count of characters 
	for (int j = 0; j < len1 ; j++) 
	{ 
		// count occurrence of characters of string 
		hash_str[str[j]]++; 

		// If string's char matches with pattern's char 
		// then increment count 
		if (hash_pat[str[j]] != 0 && 
			hash_str[str[j]] <= hash_pat[str[j]] ) 
			count++; 

		// if all the characters are matched 
		if (count == len2) 
		{ 
			// 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 ( hash_str[str[start]] > hash_pat[str[start]] 
				|| hash_pat[str[start]] == 0) 
			{ 

				if (hash_str[str[start]] > hash_pat[str[start]]) 
					hash_str[str[start]]--; 
				start++; 
			} 

			// update window size 
			int len_window = j - start + 1; 
			if (min_len > len_window) 
			{ 
				min_len = len_window; 
				start_index = start; 
			} 
		} 
	} 

	// If no window found 
	if (start_index == -1) 
	{ 
	cout << "No such window exists"; 
	return ""; 
	} 

	// Return substring starting from start_index 
	// and length min_len 
	return str.substr(start_index, min_len); 
} 

// Driver code 
int main() 
{ 
	string str = "this is a test string"; 
	string pat = "tist"; 

	cout << "Smallest window is : \n"
		<< findSubString(str, pat); 
	return 0; 
} 
Posted
Updated 9-Feb-19 11:29am

You have to think about what data each layer provides. The variable str, a string, is an array of characters. A character is just an integer of one byte. That means the value of str[j] is an integer that could range from 0 to 255, the range of one byte. That value is used to index into the hash_pat and hash_str arrays which are 256 elements in length.

It might be more clear for you if you expand the expression like this :
C++
for( int i = 0; i < len2; ++i )
{
    int index = pat[i];
    ++hash_pat[index];
}
That just takes the inner expression and saves it to a temporary variable called index but the same things are happening in this.

FWIW, if this was my code I would be using temporary variables much more. For one thing, I think it makes things easier to see in the debugger. Here's an example :
C++
for (int j = 0; j < len1 ; j++)
{
    int tempstrj = str[j];
    // count occurrence of characters of string
    hash_str[tempstrj]++;

    // If string's char matches with pattern's char
    // then increment count
    if (hash_pat[tempstrj] != 0 &&
        hash_str[tempstrj] <= hash_pat[tempstrj] )
        count++;

    // if all the characters are matched
    if (count == len2)
    {
        // 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.
        int tempstrst = str[start];
        while ( hash_str[tempstrst] > hash_pat[tempstrst]
            || hash_pat[tempstrst] == 0)
        {

            if (hash_str[tempstrst] > hash_pat[tempstrst])
                hash_str[tempstrst]--;
            start++;
        }

        // update window size
        int len_window = j - start + 1;
        if (min_len > len_window)
        {
            min_len = len_window;
            start_index = start;
        }
    }
}
   
v2
Comments
Nelek 9-Feb-19 16:26pm
   
Good explanation +5.
Rick York 9-Feb-19 21:27pm
   
Thank you.
Kohila G 10-Feb-19 0:18am
   
Clear Explanation. Thanks a lot.
Quote:
How can a character be an index to an array?

Learn about ASCII coding.

Your don't understand what this code is doing, a tool can help you to, it the debugger !

Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
   
Comments
Kohila G 10-Feb-19 0:17am
   
This is so useful. Thank you so much.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900