Remove Common Characters and Concatenate

Problem

Given two strings s1 and s2. Modify both the strings such that all the common characters of s1 and s2 are to be removed and the uncommon characters of s1 and s2 are to be concatenated.

Note: If all characters are removed print -1.

Examples:

Example 1:

Input:
s1 = aacdb
s2 = gafd
Output: cbgf
Explanation: The common characters of s1 and s2 are: a, d. The uncommon characters of s1 and s2 are c, b, g and f. Thus the modified string with uncommon characters concatenated is cbgf.

Example 2:

Input:
s1 = abcs
s2 = cxzca
Output: bsxz
Explanation: The common characters of s1 and s2 are: a,c. The uncommon characters of s1 and s2 are b,s,x and z. Thus the modified string with uncommon characters concatenated is bsxz.

Your task:

The task is to complete the function concatenatedString() which removes the common characters, concatenates, and returns the string. If all characters are removed then return -1.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O$(Number of distinct characters)

Note: N = |Length of Strings|

Constraints:

• $1<=$|Length of Strings|$<=10^4$

Solution

Python

def concatenatedString(self,s1,s2):
    freq_s1 = {}
    freq_s2 = {}
    for char in s1:
        freq_s1[char] = freq_s1.get(char, 0) + 1
    for char in s2:
        freq_s2[char] = freq_s2.get(char, 0) + 1
    result = []
    for char in s1:
        if char not in freq_s2:
            result.append(char)
    for char in s2:
        if char not in freq_s1:
            result.append(char)
    if len(result) == 0:
        return "-1"
    else:
        return "".join(result)

Java

public static String concatenatedString(String s1,String s2) {
    Map<Character, Integer> freq_s1 = new HashMap<>();
    Map<Character, Integer> freq_s2 = new HashMap<>();
    for (char ch : s1.toCharArray()) {
        freq_s1.put(ch, freq_s1.getOrDefault(ch, 0) + 1);
    }
    for (char ch : s2.toCharArray()) {
        freq_s2.put(ch, freq_s2.getOrDefault(ch, 0) + 1);
    }
    StringBuilder result = new StringBuilder();
    for (char ch : s1.toCharArray()) {
        if (!freq_s2.containsKey(ch)) {
            result.append(ch);
        }
    }
    for (char ch : s2.toCharArray()) {
        if (!freq_s1.containsKey(ch)) {
            result.append(ch);
        }
    }
    if (result.length() == 0) {
        return "-1";
    } 
    else {
        return result.toString();
    }
}

C++

string concatenatedString(string s1, string s2) { 
    unordered_map<char, int> freq_s1;
    unordered_map<char, int> freq_s2;
    for (char ch : s1) {
        freq_s1[ch]++;
    }
    for (char ch : s2) {
        freq_s2[ch]++;
    }
    string result;
    for (char ch : s1) {
        if (freq_s2.find(ch) == freq_s2.end()) {
            result += ch;
        }
    }
    for (char ch : s2) {
        if (freq_s1.find(ch) == freq_s1.end()) {
            result += ch;
        }
    }
    if (result.empty()) {
        return "-1";
    } 
    else {
        return result;
    }
}

C

char* concatenatedString(const char* s1, const char* s2) {
    Entry freq_s1[256] = {0}; 
    Entry freq_s2[256] = {0};
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    for (int i = 0; i < len1; i++) {
        freq_s1[s1[i]].key = s1[i];
        freq_s1[s1[i]].count++;
    }
    for (int i = 0; i < len2; i++) {
        freq_s2[s2[i]].key = s2[i];
        freq_s2[s2[i]].count++;
    }
    
    char* result = (char*)malloc((len1 + len2 + 1) * sizeof(char));
    int idx = 0;
    for (int i = 0; i < len1; i++) {
        if (freq_s2[s1[i]].count == 0) {
            result[idx++] = s1[i];
        }
    }
    for (int i = 0; i < len2; i++) {
        if (freq_s1[s2[i]].count == 0) {
            result[idx++] = s2[i];
        }
    }
    result[idx] = '\0'; 
    if (idx == 0) {
        strcpy(result, "-1");
    }
    return result;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O$(Number of distinct characters)