06 February 2010

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

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){
    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);
    freqMap.put(str.charAt(i), ++count);
  return freqMap;

//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115
//Input1: lsjfa9fjdsajf
//Input2: dsklajfdkl99
//Output: dslajf9



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

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