• 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

CodeChef’ RRCOPY

Python String and numbers

Sort an array according to the order defined by another array

Introduction To Number Theory ( Part 1 )

Stock Buy Sell to Maximize Profit

Right view of Binary tree

Hackerearth : Counting Subarrays

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Given a string, find the first character which is non-repetitive

SAP Off Campus Hiring_ March 2015 Sample Questions

Maximum difference between two elements s.t larger element appears after the smaller number

LeetCode: Binary Tree Maximum Path Sum

Apriori algorithm C Code Data Mining

VMWare Openings

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Max Sum in circularly situated Values

FizzBuzz Solution C C++

Trie Dictionary

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

Doubly linked list

Longest Increasing Subsequence

Templates in C++

Count number of ways to reach a given score in a game

Print vertical sum of all the axis in the given binary tree

Find the number ABCD such that when multipled by 4 gives DCBA.

flattens 2 D linked list to a single sorted link list

Code Chef PRGIFT Solution

Minimum insertions to form a palindrome

Common Ancestor in a Binary Tree or Binary Search Tree

Circular Linked List

Copyright © 2025 · Genesis Framework · WordPress · Log in