import java.util.Stack;

/**
 * 
 * One possible solution is to concatenate first and second string, then find
 * all possible anagrams of that string, and finally check if the third string
 * is present in one of the anagrams. Works! But the problem is generating the
 * anagrams. Deteriorates the complexity.
 * 
 * Another solution is to compromise of the space complexity a little, and make
 * use of a stack as below.
 */
public class CombineTwoStrings {
	public static void main(String[] args) {
		CombineTwoStrings cts = new CombineTwoStrings();
		String one = "rohit";
		String two = "deepthi";
		String combined = "rodehepitht";
		System.out.print(cts.isValid(one, two, combined));
	}

	public boolean isValid(String one, String two, String combined) {
		Stack<Character> s = new Stack<Character>();
		if ((one.length() + two.length()) != combined.length())
			return false;
		for (int i = combined.length() - 1; i >= 0; i--) {
			s.push(combined.charAt(i));
		}
		int oneIndex = 0;
		int twoIndex = 0;
		while (!s.isEmpty() && oneIndex < one.length()
				&& twoIndex < two.length()) {
			char comparer = s.pop();
			if (comparer == one.charAt(oneIndex))
				oneIndex++;
			else if (comparer == two.charAt(twoIndex))
				twoIndex++;
			else
				return false;
		}
		return true;
	}
}
@@ -1,8 +1,34 @@
+import java.util.HashMap;%0A
 import j
@@ -43,16 +43,16 @@
 .Stack;%0A
-
 %0A/**%0A * 
@@ -442,16 +442,168 @@
  below.%0A
+ * %0A * Addition: We could also use a HashMap to record the rank of each character%0A * in the combined string and check the two input strings as below.  %0A
  */%0Apubl
@@ -774,16 +774,43 @@
 epthi%22;%0A
+%09%09String three = %22viveka%22;%0A
 %09%09String
@@ -836,16 +836,52 @@
 pitht%22;%0A
+%09%09String combined2 = %22rviovehkiat%22;%0A
 %09%09System
@@ -890,16 +890,18 @@
 ut.print
+ln
 (cts.isV
@@ -927,16 +927,78 @@
 ined));%0A
+%09%09System.out.println(cts.isValidTwo(one, three, combined2));%0A%0A
 %09%7D%0A%0A%09pub
@@ -1588,9 +1588,750 @@
 rue;%0A%09%7D%0A
-%7D
+%09%0A%09// Used a hashMap to save the rank of each character in the combined string. %0A%09// Incrementing the pointer of respective string as per the rank in the %0A%09// combined string.%0A%09public boolean isValidTwo(String one, String two, String combined) %7B%0A%09%09if(one.length() + two.length() != combined.length())%0A%09%09%09return false;%0A%09%09HashMap%3CInteger, Character%3E map = new HashMap%3C%3E();%0A%09%09int key = 0, p1 = 0, p2 = 0, pT = 0;%0A%09%09for(Character i : combined.toCharArray()) %7B%0A%09%09%09map.put(key++, i);%0A%09%09%7D%0A%09%09%0A%09%09while(p1 %3C= one.length() - 1 && p2 %3C= two.length() - 1 && pT %3C= combined.length() - 1) %7B%0A%09%09%09char temp = map.get(pT++);%0A%09%09%09if(one.charAt(p1) == temp)%0A%09%09%09%09p1++;%0A%09%09%09else if (two.charAt(p2) == temp)%0A%09%09%09%09p2++;%0A%09%09%09else%0A%09%09%09%09return false;%0A%09%09%7D%0A%09%09return true;%0A%09%7D%0A%7D%0A

Update CombineTwoStrings.java