06 February 2010

Find common sequence that is out of order between two given strings in Java

Hi,
Recently i faced this question from Amazon. Given two strings, find the longest common sequence that is out of order. Initially it was royally confusing to me what the question meant, but I was able to come up with a solution. Please see the following program implemented in Java. The sample inputs and outputs have been provided at the end.
```package dsa.stringmanipulation;

import java.util.Map;

public class Sequence {
public static void main(String[] args) {
Sequence seq = new Sequence();
String str1 = "a111b3455yy";
String str2 = "byy115789";
System.out.println("Input1: "+str1);
System.out.println("Input2: "+str2);
String solution = seq.findCommonSequnce(str1, str2);
System.out.println("Output: "+solution);
}

public String findCommonSequnce(String str1, String str2){
if(str1==null || str2==null){
return "";
}
if(str1.length() == 0 || str2.length() == 0){
return "";
}
//parse first String store the frequency of characters
//in a hashmap
Map<Character,Integer> firstStringMap = frequencyMap(str1);

StringBuilder output = new StringBuilder();

for(int i=0;i<str2.length();i++){
int count = 0;
if(firstStringMap.containsKey(str2.charAt(i)) && (count=firstStringMap.get(str2.charAt(i)))>0){
output.append(str2.charAt(i));
firstStringMap.put(str2.charAt(i), --count);
}
}

return output.toString();
}

/**
* Returns a map with character as the key and its occurence as the value
* @param str
* @return
*/
private Map<Character,Integer> frequencyMap(String str) {
Map<Character, Integer> freqMap = new LinkedHashMap<Character,Integer>();
for(int i=0;i<str.length();i++){
Integer count = freqMap.get(str.charAt(i));
if(count==null){//means the frequency is yet to stored
freqMap.put(str.charAt(i), 1);
}else{
freqMap.put(str.charAt(i), ++count);
}
}
return freqMap;
}
}

//SAMPLE OUTPUTS
//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115
//
//Input1: lsjfa9fjdsajf
//Input2: dsklajfdkl99
//Output: dslajf9```

Cheers,

Unknown said...

hi Brag...It awesome program..just wants to know i don't think its necessary to use this line
(count=firstStringMap.get(str2.charAt(i)))>0) ..????

BragBoy said...

@shashank : Errrr.. I see why do ask this question. I am assigning count to 0 before that line and using this to simply assign to a variable and check it. Its a bit dirty there, you could avoid that condition. But still the condition check for > 0 is still needed.

nagarajan said...

Here comes an equivalent C program

Let me know if it has some bugs

#include
int main()
{
char *a="lsjfa9fjdsajf";
char *b="dsklajfdkl99";
int str1[256]={0};
int i;

for(i=0;i<strlen(a);++i)
str1[a[i]]++;

for(i=0;i<strlen(b);++i)
if(str1[b[i]])
{
putchar(b[i]);
str1[b[i]]--;
}
getchar();
}