Data Structures and Algorithms for Geeks: Algo#48: Find minimum window length which accommodate all given character.
E.g. Given string ABBACBAA, and if we want to find minimum window length which can accommodate "AAA", it will be 5 (index 3 to 7). "CCC" should return MAX length as no window in original string can accommodate "CCC".
Read full article from Data Structures and Algorithms for Geeks: Algo#48: Find minimum window length which accommodate all given character.
Given problem is purely string manipulation problem. Here we have to find minimum window length which accommodate all given character for second string.
E.g. Given string ABBACBAA, and if we want to find minimum window length which can accommodate "AAA", it will be 5 (index 3 to 7). "CCC" should return MAX length as no window in original string can accommodate "CCC".
int min_window(char *arr,char *search) |
16 | { |
17 | int arrlen = strlen(arr); |
18 | int searchlen = strlen(search); |
19 | int i=0; |
20 |
21 | if(searchlen > arrlen) |
22 | return -1; //cann't be accomodated |
23 |
24 | // we will use something like hashtable to count occurance using simple array |
25 |
26 | int shouldfind[MAX] = {0,}; |
27 | int hasfound[MAX] = {0,}; |
28 |
29 | //PART-1: FILL HASH ARRAY WITH SHOULD FIND COUNT |
30 | for(i=0;i<searchlen;i++) |
31 | { |
32 | shouldfind[search[i]] += 1; |
33 | } |
34 |
35 | int foundcount = 0; |
36 | int minWinLen = INT_MAX; |
37 | int currWinStart = 0; //end won't be needed as 'i' will work as end marker of curr window |
38 |
39 | //PART-2: Search on main string array from start |
40 | for(i=0;i<arrlen;i++) |
41 | { |
42 | //CASE 2.1: if arr[i] char is not needed, just skip it |
43 | if(shouldfind[arr[i]] == 0 ) |
44 | { |
45 | continue; |
46 | } |
47 | else |
48 | { |
49 | hasfound[arr[i]] += 1; |
50 | } |
51 |
52 |
53 | //CASE 2.2: TRICKY :increment found count only if shouldfind is greater than hasfound, bcoz unneccessary incrementing on duplicate is not desirable |
54 | if( hasfound[arr[i]] <= shouldfind[arr[i]]) |
55 | { |
56 | foundcount++; |
57 | } |
58 |
59 | //CASE 2.3: if all elemement that needs to be search are found.. |
60 | if(foundcount == searchlen) |
61 | { |
62 |
63 | //SUBCASE 2.3.1 : remove all unecessary/duplicate front element and shift window right side amap |
64 | while( !shouldfind[arr[currWinStart]] || |
65 | shouldfind[arr[currWinStart]] < hasfound[arr[currWinStart]]) |
66 | { |
67 | // removing duplicate.. |
68 | if( shouldfind[arr[currWinStart]] < hasfound[arr[currWinStart]]) |
69 | hasfound[arr[currWinStart]] -= 1; |
70 | //Increment windows start position by 1 bcoz decrementing overall window from front |
71 | currWinStart++; |
72 | } |
73 |
74 | //CASE 2.3.2 : size of minWinLen needs to be updated.. |
75 | if( minWinLen > ( i - currWinStart + 1) ) |
76 | { |
77 | minWinLen = i - currWinStart + 1; |
78 | } |
79 | } |
80 |
81 | } |
82 |
83 | return minWinLen; |
84 | } |
