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.LinkedHashMap;
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,
Bragaadeesh.

3 comments:

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...

Hi Bragadeesh,

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();
}