7 replies to this topic

[Roger]

How would you write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a? Write a version which is order N-squared and one which is order N.

Any language (or pseudo-code) is fine.

Edited by Roger, 23 August 2010 - 08:45 AM.
added order N.

[WingedPanther]

n-Squared is just a nested for loop. What's the other order you wanted?

[Roger]

Edit: Write a version which is order N-squared and one which is order N.

[zoranh]

Sorry, is the question to return the longest subset of characters in a which appear in b in the same order or the question is something else?

[abzero]

I read that as if I had two strings:
a b c
a b

then it would output a & b.

I can see the n^2 case easily enough; the n case I can only see if the strings were already sorted...

O(n^2):

foreach Char in A
    foreach Char2 in B
        if ( Char == Char2 ) print Char;

(need to eliminate dups though)

O(N) : (if there sorted)

   let b_i 0
   let a_i 0

   while ( a_i < length(A) && b_i < length(B))
   {
       if( A_{a_i} == B_{b_i} ) {
           output A_{a_i}
      
           let curChar A_{a_i}

           while ( B_{b_i}==curChar && b_i<length(B) ) increment b_i;
           while ( A_{a_i}==curChar && a_i<length(A)) increment a_i;
       } else {
           increment a_i;
       }
}

I'm sure a smart brain has the solution here.

[zoranh]

O(n^2) is a dynamic programming solution to Longest Common Subsequence problem. It's not trivial to code if you actually need to print the subsequence (it's twice more work to do compared to just calculating the length of LCS).

Second part of the question - to find it in O(n) - I'm not aware of existence of LCS algorithm that would do it, even with knowledge that characters belong to quite a limited alphabet.

Again, all I said is in case that longest common subsequence is requested, though it doesn't say so in the original post.

[rwvo]

The question doesn't seem to ask for LCS, just for a string of characters that appear in both strings; the characters in the resulting string should appear in the order in which they appear in a.

For example, a = "abcd", b = "dacdadd" -> acd.

(this interpretation of the question assumes that characters in the first string are unique, which is not stated in the question).

Given this interpretation, a linear time solution would be:
* count the characters in b using a hash table
* for each character in a, look up its count in b using the hash table, and print it if the count is greater than zero.

[zoranh]

rwvo is correct, that is the solution. I've coded that, plus a full O(n^2) solution which prints the same result.

First note that every O(n) solution is also O(n^2), so once you solve O(n), you can just say - it's O(n^2) as well.

But if you really want to code a Omega(n^2) solution, i.e. solution which really runs in C*n^2 time, then you can do this:
- for each character in a count how many occurrences of that character there are from the beginning of a
- then iterate through b and count if there are at least as many occurrences of that character in b
- if there are enough occurrences of the character in b, then print it.

Here is the code in C# which first implements O(n) solution and then O(n^2). Both solutions return longest possible substring of a and both should print the same string as a result:

using System;
using System.Collections.Generic;

namespace Test
{

    class Program
    {

        static void Main(string[] args)
        {

            Console.Write("Enter a: ");
            string a = Console.ReadLine();

            Console.Write("Enter b: ");
            string b = Console.ReadLine();

            int range = (int)char.MaxValue - (int)char.MinValue + 1;
            Dictionary<char, int> count = new Dictionary<char, int>();

            char[] arrayA = a.ToCharArray();
            char[] arrayB = b.ToCharArray();

            for (int i = 0; i < arrayB.Length; i++)
            {
                if (count.ContainsKey(arrayB[i]))
                    count[arrayB[i]]++;
                else
                    count[arrayB[i]] = 1;
            }
            Console.Write("Common substring: '");

            for (int i = 0; i < arrayA.Length; i++)
            {
                if (count.ContainsKey(arrayA[i]) && count[arrayA[i]] > 0)
                {
                    Console.Write(arrayA[i]);
                    count[arrayA[i]]--;
                }
            }

            Console.WriteLine("'");

            // Now O(n^2) solution

            Console.Write("Common substring: '");

            for (int i = 0; i < arrayA.Length; i++)
            {
                
                int k = 0;
                for (int j = 0; j <= i; j++)
                    if (arrayA[j] == arrayA[i])
                        k++;

                for (int j = 0; j < arrayB.Length; j++)
                    if (arrayB[j] == arrayA[i])
                        k--;

                if (k <= 0)
                    Console.Write(arrayA[i]);

            }

            Console.WriteLine("'");
            
        }

    }

}