mithya
BAN USERAssuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
I don't think you can solve this without using encoding. See my answer with encoding.
- mithya February 20, 2015