# Uses Longest Increasing Subsequence & Subset Enumeration (DFS)

• My solution finds the longest matching pattern of string 1 in string 2.
So for word1 = "adbac" and word2 = "abc" , the longest matching pattern (not necessarily continuous) is "abc"
How ? we can remove 'd' & second 'a' from "adbac" to get "abc".
The way I find the longest matching pattern is through longest increasing subsequence . (standard dp)
After than, the minimum can be found using simple math.

``````public class Solution {

List<List<Integer>> sequences = new ArrayList<List<Integer>>();
void printer(List<Integer> seq){
for(int i=0;i<seq.size();i++)
System.out.print(seq.get(i) + " ");
System.out.println();
}
void form(int cur,List<Integer> sequence,List<List<Integer>>array){
if(cur == array.size()){
List<Integer> copy = new ArrayList<Integer>();
for(int i=0; i<sequence.size();i++)
return;
}
List<Integer> options = array.get(cur);
for(int i=0;i<options.size();i++){
form(cur+1,sequence,array);
sequence.remove(sequence.size()-1);
}
}

# find longest increasing subsequence for a given sequence
List<Integer> get_lis (List<Integer> sequence){
List<Integer> dp = new ArrayList<Integer>();
Map<Integer,Integer> path = new HashMap<Integer,Integer>();
List<Integer> lis = new ArrayList<Integer>();
path.put(0,-1);
int maxpos = 0;
for(int i=1;i<sequence.size();i++){
if(sequence.get(i) == -1){
continue;
}
path.put(i,-1);
for(int j=0;j<i;j++){
if(sequence.get(j) < sequence.get(i) && dp.get(j) >= dp.get(i)){
dp.set(i,dp.get(j)+1);
path.put(i,j);
}
}
if(dp.get(i)>dp.get(maxpos))
maxpos = i;
}
Set<Integer> in_lis = new HashSet<Integer>();
int pos = maxpos;
while(true){
if(pos == -1)
break;
pos = path.get(pos);
}
int count = 0;
for(int i=0;i<sequence.size();i++){
if(in_lis.contains(i)){
count++;
}
else
}
return lis;
}

public int minDistance(String word1, String word2) {

# form a map from characters that appear in word2 to a list of indices they appear in

HashMap<Character,List<Integer>> map = new HashMap<Character,List<Integer>>();
for(int i=0;i<word2.length();i++){
char c = word2.charAt(i);
if(!map.containsKey(c)){
ArrayList<Integer> l = new ArrayList<Integer>();
map.put(c,l);
}
else{
List<Integer> l = map.get(c);
}
}

# form a map from each index in word1 to the possible positions of that character in word2
List<List<Integer>> array = new ArrayList<List<Integer>>();
for(int i=0;i<word1.length();i++){
char c = word1.charAt(i);
List<Integer> l;
if(!map.containsKey(c)){
l = new ArrayList<Integer>();
}
else
l = map.get(c);
}

List<Integer> sequence = new ArrayList<Integer>();      #empty sequence just for the purpose of DFS

# from the above map, each index in word1 can have multiple values. For example, for word1 = "abc"
and word2 = "aad" , the values for index 0 ('a') for word1 are 0 and 1, because  'a' appears at
indices 0 and 1 in word2. So we form all sequences for all possible values of each index of word1.

form(0,sequence,array);                 # form all possible sequences

# the following part gets the maximum longest possible subsequence from all possible sequences
List<Integer> final_lis = new ArrayList<Integer>();
int maxlen=0;
for(int i=0; i<sequences.size();i++){
sequence = sequences.get(i);
List<Integer> lis = get_lis(sequence);
int lislen = lis.get(lis.size()-1);
if(lislen>maxlen){
maxlen = lislen;
lis.remove(lis.size()-1);
final_lis = lis;
}
}

#simple math to get the final answer
int i=0;
int previ=0;
int prevval=0;
while(i<final_lis.size()){
if(final_lis.get(i) == -1){
i++;
continue;
}

int diff1 = final_lis.get(i) - prevval -1;
int diff2 = i - previ -1;
previ = i;
prevval = final_lis.get(i);
i++;
}

int diff1 = word1.length() - previ;
int diff2 = word2.length() - prevval;