• 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

Client Server C program

Find Percentage of Words matching in Two Strings

LeetCode: Binary Tree Maximum Path Sum

Find two non repeating elements in an array of repeating elements

Max Sum in circularly situated Values

Serialise Deserialise N-ary Tree

Doubly linked list

VMWare SDEII Interview

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Generate largest number arranging a no. of given non negative integer numbers

Add Sub Multiply very large number stored as string

Find the element that appears once others appears thrice

Possible sizes of bus to carry n groups of friends

VMWare Openings

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

simple sql injection

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

Count Possible Decodings of a given Digit Sequence

SAP Interview Questions

1014 Practice Question of New GRE – Princeton

Amazon Interview On-Campus For Internship – 1

Trapping Rain Water

How Radix sort works

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

Convert number to words java

CodeChef Code SGARDEN

Reversal of LinkedList

Printing each word reverse in string

CodeChef’ RRCOPY

Wrong Directions given find minimum moves so that he can reach to the destination

Copyright © 2025 · Genesis Framework · WordPress · Log in