• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find the smallest window in a string containing all characters of another string

January 12, 2015 by Dhaval Dave

Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.For Example:

Input string1: “this is a test string”
Input string2: “tist”

Output string: “t stri”


Method 1 ( Brute force solution )
a) Generate all substrings of string1 (“this is a test string”)
b) For each substring, check whether the substring contains all characters of string2 (“tist”)
c) Finally print the smallest substring containing all characters of string2.

Method 2 ( Optimized Brute Force ) 
a)  calculate positions of characters of String2(“tist”) from String1 (“this is a test string”)
that is
postition[‘t’] = {0,10,13, 16}
postition[‘i’] = {2,5,18}
postition[‘s’] = {3,6,12,15}

b) permutations = positions[‘t’] * positions[‘i’] * positions[‘s’] * positions[‘t’] ie : permutation = { { 0, 2,3,10} , {0,5,6,10} …… }
Find the one which has smallest gap in all …
ie : {13,18,15,16}
(This we can find from min in set and max in set.)

Method 3) Create Table for index and find 

– Take help of two pointers “begin” and “end” position of the window. Two tables “needToFind” and “hasFound” while traversing String1.
– “needToFind” stores the total count of a character in String2(“tist”) and “hasFound” stores the total count of a character met so far from String1(“this is …”)
– keep “count” variable to store the total characters in String2 that’s met so far (not counting characters where hasFound[x] exceeds needToFind[x])

Procedure

– We Start checking String1 from begin & end as 0,0 window to 0,strlen(String1) length.
– When ever we find a character need to be in String2.
We check count of occurance
if its >= needing count (needToFind) then we increment count.

When found are matching needTofind window fully
ie . all character of String2 are in 0 to t index of Sting1
like in out example “this is a t”
we store total count.
– now we increase begin and see if new window contains all character count needing.
and we proceed

else we increment end ( maximizing the window..)

Check Workig Code at http://ideone.com/79jBH9



Function :

bool minWindow(const char* S, const char *T, int &minWindowBegin, int &minWindowEnd) {
  int sLen = strlen(S);
  int tLen = strlen(T);
  int needToFind[256] = {0};

  for (int i = 0; i < tLen; i++)
    needToFind[T[i]]++;

  int hasFound[256] = {0};
  int minWindowLen = INT_MAX;
  int count = 0;
  int begin,end,windowLen;
  for (begin = 0, end = 0; end < sLen; end++) {

    if (needToFind[S[end]] == 0) continue;
    hasFound[S[end]]++;
    if (hasFound[S[end]] <= needToFind[S[end]])
      count++;


    if (count == tLen) {

      while (needToFind[S[begin]] == 0 || hasFound[S[begin]] > needToFind[S[begin]]) {
        if (hasFound[S[begin]] > needToFind[S[begin]])
          hasFound[S[begin]]–;
        begin++;
      }

      windowLen = end – begin + 1;
      //cout<<windowLen<<endl;
      if (windowLen < minWindowLen) {
        minWindowBegin = begin;
        minWindowEnd = end;
        minWindowLen = windowLen;
      } // end if
    } // end if
  } // end for
  
  //seeting end limit if we found such window
 if(count == tLen){
  while(1){
  if (needToFind[S[end]] == 0) end–;
  else break;
  }//while
  cout<<begin<<“-“<<end<<endl;
  return true;
}//if
return false;  
}
int main() {
// your code goes here
int begin=0, end=0;
cout<<minWindow(“this is a test string”,”tist”,begin, end);
return 0;
}

If you want to share such question , solution  or your experience of any company, Please do share at admin@gohired.in , As sharing is caring

Similar Articles

Filed Under: Amazon Interview Question, Hacker Earth Questions, Interview Questions, problem Tagged With: Dynamic Programming, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Memory Efficient LinkedList

Printing each word reverse in string

Check if an array has duplicate numbers in O(n) time and O(1) space

Find Nearest Minimum number in left side in O(n)

Get K Max and Delete K Max in stream of incoming integers

Sequence Finder Dynamic Programming

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Given a float number convert it into the string WITHOUT using any inbuilt Function

Trie Dictionary

Sort an array according to the order defined by another array

Implement a generic binary search algorithm for Integer Double String etc

Max Sum in circularly situated Values

Generate next palindrome number

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Maximum occurred Smallest integer in n ranges

SAP Hiring Off-Campus General Aptitude

Diagonal Traversal of Binary Tree

Connect n ropes with minimum cost

Level order traversal in Spiral form

Daughter’s Age VeryGood Puzzle

Find Pythagorean Triplets in an array in O(N)

Naurki.com Security Breach

Amazon Interview On-Campus For Internship – 1

25 horses 5 tracks Find 3 fastest puzzle

Linked List V/S Binary Search Tree

Flipkart SDET Interview Experience

Mirror of Tree

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

LeetCode : Word Search

Implement LRU Cache

Copyright © 2025 · Genesis Framework · WordPress · Log in