• 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

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

Binary Tree in Java

Closed Parentheses checker

Given Set of words or A String find whether chain is possible from these words or not

Code Chef PRGIFT Solution

C++ OOPs Part1

Linked List V/S Binary Search Tree

Reverse a Linked List in groups of given size

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Sort Stack in place

Connect n ropes with minimum cost

The greedy coins game Dynamic Programming

Leetcode: Merge Intervals

Find loop in Singly linked list

Convert number to words java

Find the element that appears once others appears thrice

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

SAP Interview Questions

Python Dictionaries

Test Cases for Round Function

Knight Tour Problem (Graph – Breadth First Search)

1014 Practice Question of New GRE – Princeton

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

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Printing Longest Common Subsequence

Doubly linked list

Microsoft BING Interview Experience

Python List

Templates in C++

Urban Ladder Written Test.

Copyright © 2025 · Genesis Framework · WordPress · Log in