## Saturday, 8 February 2014

### Finding minimum window containing given subsequence

#### Question :

It was long description for a DNA problem. Main DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPat). You have to find the minimum length window in strDNA where strPat is subsequence. (GeeksForGeeks)

#### Code :

```package Miscellaneous;

/**
* Created by Aniket on 2/8/14.
*/
public class SmallestCommonSubSequenceFinder {

String strDna;
String strPat;

char[] patternArray;
char[] dnaArray;

int bestLength;
int bestStart;
int bestEnd;

public int getBestEnd() {
return bestEnd;
}

public void setBestEnd(int bestEnd) {
this.bestEnd = bestEnd;
}

public int getBestStart() {
return bestStart;
}

public void setBestStart(int bestStart) {
this.bestStart = bestStart;
}

public int getBestLength() {
return bestLength;
}

public void setBestLength(int bestLength) {
this.bestLength = bestLength;
}

public SmallestCommonSubSequenceFinder(String strDna, String strPat){
this.strDna = strDna;
this.strPat = strPat;
this.patternArray = strPat.toCharArray();
this.dnaArray = strDna.toCharArray();
}

public int getStartIndex(int start){
for(int i=start;i<dnaArray.length;i++){
if(dnaArray[i] == patternArray[0]){
return i;
}
}
return -1;
}

public void findMinSubSeqDNAWindow(int start,int currIndex, int comparingIndex, boolean isStart){

if(start >= dnaArray.length || currIndex >= dnaArray.length){
return;
}

while(currIndex < dnaArray.length && dnaArray[currIndex] != patternArray[comparingIndex]){
currIndex++;
}

//check if currIndex has exceeded the array length

if(currIndex >= dnaArray.length){
return;
}

if(isStart){
start = currIndex;
isStart = false;
}

if(comparingIndex == patternArray.length-1){
int lengthOfSubSeq = currIndex - start + 1;
if(bestLength == 0 || lengthOfSubSeq < bestLength){
bestLength = lengthOfSubSeq;
bestStart = start;
bestEnd = currIndex;
}
//start finding new sub sequence
findMinSubSeqDNAWindow(start + 1, start + 1, 0, true);
}
else {
//go for next character
findMinSubSeqDNAWindow(start, currIndex+1, comparingIndex+1, isStart);
}
}

public static void main(String args[]){
String strPat = "bdf";
String strDna = "abcdefgbdf";

SmallestCommonSubSequenceFinder finder = new SmallestCommonSubSequenceFinder(strDna,strPat);
finder.findMinSubSeqDNAWindow(0,0,0,true);
System.out.println("Best Length : " + finder.getBestLength());
System.out.println("BestStart : " + finder.getBestStart());
System.out.println("Best End : " + finder.getBestEnd());
}
}
```

Best Length : 3
BestStart : 7
Best End : 9

#### 1 comment:

1. #include
#include
using namespace std;

int findMinWindow(char sub[],char parent[],int ls,int lp)
{
cout << "searching " << sub << " in " << parent << endl;
int x,y;
x=y=0;
bool matchStart = false;
int len = 0;
int temp = -1;
while(x 0 && (parent[x] == sub[0]))
{
int newTemp = findMinWindow(sub,parent+x,ls,lp-x);
if(temp == -1)
{
temp = newTemp;
}else{
temp = min(temp,newTemp);
}
}

if(y > 0)
{
len++;
}

if(y == ls)
{
cout << "returning nor " << len < 0)
cout << "found length " << found;
else