Mailman
BAN USERCorrected a few bugs .Here is the running C version of your code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int findMinWindow(const char *S, const char *T,int* begin,int* end);
void main()
{
int begin=0,end =0;
int minLength=0;
const char*S ="adobecodebanc";
const char *T="abc";
minLength=findMinWindow(S,T,&begin,&end);
printf("minLength=%d,begin=%d,end=%d \n",minLength,begin,end);
printf("\nPrinting Min Sub String\n");
for(int i=0;i<minLength;i++)
printf("%c",S[begin+i]);
}
int findMinWindow(const char *S, const char *T,int * begin,int* end ){
int SLen = strlen(S);
int TLen = strlen(T);
// Declare 2 arrays which keep tab of required & found frequency of each char in T
int isReq[256] ;
int isFound[256];
memset(isReq,'0',sizeof(isReq));
memset(isFound,'0',sizeof(isFound));
int count = 0; //For valid window
int minWindow = INT_MAX;
//Prepare the isReq[] array by parsing the T
for(int i=0;i<TLen;i++){
isReq[T[i]]++;
}
//Let's start parsing the S now; Take 2 pointers: i and j - both starting at 0
int i=0, j=0;
//Keep moving j forward, keep i fixed till we get a valid window
for(int c=j;c<SLen;c++,j++){
//Check if the character read appears in T or not
if(isReq[S[c]] == 0){
//This character does not appear in the T; skip this
continue;
}
//We have this character in the T, lets increment isFound for this char
isFound[S[c]]++;
//increment the count if this character satisfies the invariant
if(isFound[S[c]] <= isReq[S[c]]){
count++;
}
//Did we find a valid window yet?
if(count == TLen){
//A valid window is found..lets see if we can do better from here on
//better means: increasing i to reduce window length while maintaining invariant
while(isReq[S[i]] == 0 || isFound[S[i]] > isReq[S[i]]){
//Either of the above 2 conditions means we should increment i; however we
// must decrease isFound for this char as well.
//Hence do a check again
if(isFound[S[i]] > isReq[S[i]]){
isFound[S[i]]--;
}
i++;
printf("\nIn while loop %c,i=%d,S[c]=%c,c=%d",S[i],i,S[c],c);
}
// Note that after the while loop, the invariant is still maintained
// Lets check if we did better
int winLength = j-i+1;
printf("\nwinLength=%d \n",winLength);
if(winLength < minWindow){
//update the references we got
*begin = i;
*end = j;
//Update new minimum window length
minWindow = winLength;
// printf("\nminWindow=%d",minWindow);
}
} //End of if(count == TLen)
} //End of for loop
return minWindow;
}
C code O(n)
#include "stdio.h"
#include "stdlib.h"
#define LENGTH 10
void main()
{
int a[10]= {1,0,3,4,5,0,7,8,0,10};
int start=0;
int end =LENGTH-1;
int temp;
while(start < end){
// set the end to a non zero element
while (a[end]==0) end--;
if (a[start]==0)
{
// swap the 0 with the end element
temp=a[end];
a[end]=a[start];
a[start]=temp;
}
start++;
} // end while
printf(" Array after processing is ");
for(int i=0;i<LENGTH;i++)
{
printf(" %d ",a[i]);
}
}
resubmitting code
#include "stdio.h"
#include "stdlib.h"
int BinarySearch(int[],int,int,int);
void main()
{
int CurrentPos=0,StartPos=0,EndPos=0;
int FindElement=0,Start,End,ArraySize;
int a[] ={1,2,3,4,5,5,5,5,6,7};
ArraySize=sizeof(a)/sizeof(int);
FindElement=5;
Start=0;
End=ArraySize;
CurrentPos=BinarySearch(a,FindElement,Start,End);
StartPos=CurrentPos;
EndPos=CurrentPos;
while(StartPos!=0)
{
if(a[StartPos-1]==a[StartPos])
{
StartPos--;
}
else{
break;
}
}
while(EndPos!=ArraySize-2)
{
if(a[EndPos+1]==a[StartPos])
{
EndPos++;
}
else{
break;
}
}
printf("%d's start position is %d ending position is %d",FindElement,StartPos,EndPos );
}
int BinarySearch(int a[],int FindElement,int Start,int End){
int MidPoint= (Start+End)/2;
if(a[MidPoint]==FindElement)
{
return MidPoint;
}
else if (a[MidPoint]>FindElement)
{
BinarySearch(a,FindElement,Start,MidPoint);
}
else if (a[MidPoint]<FindElement)
{
BinarySearch(a,FindElement,MidPoint,End);
}
}
int[] a ={1,2,3,4,5,5,5,5,6,7}
For example: we need to find the start and end position of 5.
Perform a binary search to find 5
Once 5 is found, lets call it currentpos
From currentpos move towards start of the array to find an element that is different from 5 .
From currentpos move towards the end of the array to find an element that is different from 5
#include "stdio.h"
#include "stdlib.h"
int BinarySearch(int[],int,int,int);
void main()
{
int CurrentPos=0,StartPos=0,EndPos=0;
int FindElement=0,Start,End,ArraySize;
int a[] ={1,2,3,4,5,5,5,5,6,7};
ArraySize=sizeof(a)/sizeof(int);
FindElement=7;
Start=0;
End=ArraySize;
CurrentPos=BinarySearch(a,FindElement,Start,End);
StartPos=CurrentPos;
EndPos=CurrentPos;
while(StartPos!=0)
{
if(a[StartPos-1]==a[StartPos])
{
StartPos--;
}
else{
break;
}
}
while(EndPos!=ArraySize-2)
{
if(a[EndPos+1]==a[StartPos])
{
EndPos++;
}
else{
break;
}
}
printf("%d's start position is %d ending position is %d",FindElement,StartPos,EndPos );
}
int BinarySearch(int a[],int FindElement,int Start,int End){
int MidPoint= (Start+End)/2;
if(a[MidPoint]==FindElement)
{
return MidPoint;
}
else if (a[MidPoint]>FindElement)
{
BinarySearch(a,FindElement,Start,MidPoint);
}
else if (a[MidPoint]<FindElement)
{
BinarySearch(a,FindElement,MidPoint,End);
}
}
if{
}else
if (a[startpos-1]==a[startpos])
{
startpos--;
}
We could have 2 sub strings with the same count of characters as in s2 but different lengths.May be that's what the problem is about.Of course the largest substring with at least the characters in substr would be s1 as you mentioned.
- Mailman November 20, 2015