Apr 242013
 

Given two strings, write a function which will print characters coming on only one of the two strings (and not both). The character may be repeated in that string. For example:

String-1   String-2        Output
---------  ----------      -------------
AFW        BGF             AWBG
AFAAW      BGFFB           AWBG
           BGF             AWBG
AFW        BGH             AFWBGH
AFW        BGF             AWBG

Solution:

Method-1: Brute-Force Method

The brute force method is:

Step-1: Traverse String-1 and for each character in String-1 
    - Check if that char exist in String-2
    - Check if that char exists in in String-1 before the position of current char 
      (to avoid printing duplicates from a string).
  If the char is not present in any of the two, then print that character.

Step-2: Traverse the String-2 and for each character in string-2
    - Check if that char exist in String-1
    - Check if that char exists in in String-2 before the position of current char 
      (to avoid printing duplicates from a string).
  If the char is not present in any of the two, then print that character.

This method requires O(1) extra space, but its time complexity is O(n2), where n is the number of characters in each string. (If number of char is m & n, then the complexity will be O(max(mn, nm)) ).

Method-2: Using Hash

This method uses hash to store if the character is present in String-1 (String-2). Lets have an array of 26 int, which will act as a hash

int hash[26] = {0};

All elements of the array are initially zero. The Algorithm will work as follows:

Step-1: Traverse String-1, and for each char in String-1, set its count as 1 
       (we will set it as 1, even if the char is repeated multiple times in the string).

Step-2: Traverse String-2, for each char, check the value in the hash:

    // If character was present in the first string
    If(hash[str-2[i]] == 1)
        hash[str-2[i]] = -1;

    // -1 will indicate that character is present in both the strings.
    // If character was not present in the first string, then we will have to print the character
    If(hash[str-2[i]] == 0)
        hash[str-2[i]] = 2;

    After performing the above two steps the hash value for a character will be one of the following:

    0 - Char not present in any of the two strings. 
    -1 - Char present in both the strings 
    1 - Char present in only 1st string 
    2 - Char present in only 2nd string

Step-3: Now we have to just traverse the two strings, and for each character we will have to see the hash value, 
   if the value is 1 (for string-1) or 2 (for string-2), then we will print that character, else don't print the char.

Time Complexity:O(n), where n= number of characters in each string. If number of characters is different (say m & n) then the complexity will be O(max(m,n))

Extra Space Used: Constant (since the number of unique characters will be constant, size of hash will not vary w.r.t size of the two strings)

Code:

/** Assumption - The string only have characters 'A' - 'Z'
 * NOTE: IT DOES NOT EVEN HAVE lower case characters.
 * THE LOOK-UP CAN BE CHANGED CORRESPONDINGLY FOR
 * STRINGS WITH CHARACTERS OTHER THAN ['A'-'Z']
 */

void printUnique(char* str1, char* str2)
{
    // Both Strings are EMPTY
    if(str1 == NULL && str2 == NULL)
        return;

    // One of the 2 strings is EMPTY
    if(str1 == NULL) cout<< str2;
    if(str2 == NULL) cout<< str1;

    int count[26] = {0};
    int i=0;

    for (i=0; str1[i] != '\0'; i++) {
        if(count[str1[i]-'A'] == 0 )
            count[str1[i]-'A'] = 1;
    }

    for (i=0; str2[i] != '\0'; i++) {
        if(count[str2[i]-'A'] == 0 )
            count[str2[i]-'A'] = 2; // CHAR NOT PRESENT IN str1
        else if(count[str2[i]-'A'] == 1)
            count[str2[i]-'A'] = -1;
    }

    // At this point the value of count will indicate:
    //   0 - Character not present in either
    //  -1 - Duplicate across strings
    //   1 - Char present only in str1
    //   2 - char present only in str2

    cout << "\nUnique Characters are :"<<endl;

    // Printing unique chars from str1
    for (i=0; str1[i] != '\0'; i++) {
        if(count[str1[i]-'A'] == 1)
        {
            cout << " " << str1[i];
            count[str1[i]-'A'] = 0; // doesn't print duplicates
        }
    }

    // Printing unique chars from str1
    for (i=0; str2[i] != '\0'; i++) {
        if(count[str2[i]-'A'] == 2)
        {
            cout << " " << str2[i];
            count[str2[i]-'A'] = 0;
        }
    }
}

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)