• 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

Find the element that appears once others appears thrice

Printing each word reverse in string

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

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

Interfaces in C++ (Abstract Classes in C++)

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Minimum insertions to form a palindrome

Microsoft BING Interview Experience

How strtok() Works

ADOBE Aptitude C Language Test

C Program for TAIL command of UNIX

Diagonal Traversal of Binary Tree

Doubly linked list

Find two non repeating elements in an array of repeating elements

Maximum occurred Smallest integer in n ranges

Calculate price of parking from parking start end time prices

Maximum sum contiguous subarray of an Array

Printing intermediate Integers between one element & next element of array

Flipkart SDET Interview Experience

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

Common Ancestor in a Binary Tree or Binary Search Tree

Password Predictor

Find the kth number with prime factors 3, 5 and 7

Knight Tour Problem (Graph – Breadth First Search)

TicTacToe Game As Asked in Flipkart

Count Possible Decodings of a given Digit Sequence

Generic Object Oriented Stack with Template

Find if a binary tree is height balanced ?

Binary Tree in Java

Copyright © 2025 · Genesis Framework · WordPress · Log in