Strings | Smallest Window | THE INQUISITIVE

Smallest Window

LEVEL:Beginner

Description

Given two string K and L. You have to find the smallest window such that it contains all the characters of L.

Input Format

First line contains the string K. Next line contains the string L.

Output Format

Print the smallest window that contains all the characters of L.

Example 1:

Input

maximum
aim

Output

maxi

Example 2:

Input

knowledge is divine
eleven

Output

ledge is divin

Example 3:

Input

he is my favourite hero
eat

Output

avourite

Approach

Approach 1: using brute force

i)assign string 1 to another string answer
ii)assign 1 to i
iii) assign 0 to j
iv)assign j + i - 1 to k and create a empty string check
v)append all the characters from position j to k of first string to check
vi)assign 0 to count
vii) assign 0 to a
viii) assign 0 to b
ix) if character at a of check is equal to character t b of string two increment count and go to step xii
x)increment b by one value
xi) repeat ix and x till b is less than length of string 2
xii)increment value of a by one value
xiii) repeat steps viii to xii till a is less than length of the string check
xiv) if count is equal to length of second string and length of string check is less than length of answer string assign
check to answer
xv)increment j by one value
xvi)repeat steps iv to xv till j is less than length of first string
xvii)increment i by one value
xviii)repeat steps iii to xvii till x is less than length of first string
xix)return answer

Time Complexity: O(n^2 * m^2) where n and m are length of two strings
Space Complexity: O(n)

Approach 2: using hashing

i) get the lengths of two strings and store in len1 and len2
ii)if len1 is less than len2 return no window exits
iii)create two array of integers of size 256 as total no of characters are 256
iv)traverse the second string
v)increment the value of hash2 at index equal to ascii value of character of string
vi)assign 0 to start and count, -1 to index variable and max possible integer value to length variable
vii) assign 0 to j
viii) increment the value of hash array at index equal to ascii value of character at ith position of string1
ix)if value of hash2 at index equal to ascii value of character at j is not zero and
value of hash1 at index equal to ascii value of char at j of string one is less than or equal to
value of hash2 at index equal to ascii value of char at j of stirng one increment count by one value
x) if count equal to length go to next step else go step
xii) if value of hash1 at index equal to ascii value of character at start of string one is greater than
value of hash2 at index equal to ascii value of character at start of string one increment start by one value
xiii)repeat step xii till value of hash1 at index equal to ascii value of character at start of string one is greater than
value of hash2 at index equal to ascii value of character at start of string one or
value of hash2 at index equal to ascii value of character at start of string one is zero increment start by one value
xiv) assign j-start + 1 to win_len variable
xv) if length is greater than win_len assign win_length to length and start to index
xvi)increment j by one value
xvii)repeat steps viii to xvi till j is less than length of first string
xviii)if index equal to -1 return "no such window exists
xix)return substring of first string from position index to index + length

Time Complexity:O(n)
Space Complexity:O(1)

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Smallest Window

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Strings

Beginner