Uncommon Characters

Problem

Given two strings A and B consisting of lowercase english characters. Find the characters that are not common in the two strings.

Note: Return the string in sorted order.

Examples:

Example 1:

Input:
A = geeksforgeeks
B = geeksquiz
Output: fioqruz
Explanation: 
The characters 'f', 'i', 'o', 'q', 'r', 'u','z' are either present in A or B, but not in both.

Example 2:

Input:
A = characters
B = alphabets
Output: bclpr
Explanation: The characters 'b','c','l','p','r' are either present in A or B, but not in both.

Your task:

You dont need to read input or print anything. Complete the function UncommonChars() which takes strings A and B as input parameters and returns a string that contains all the uncommon characters in sorted order. If no such character exists return "-1".

• Expected Time Complexity: $O(M+N)$, where M and N are the sizes of A and B respectively.
• Expected Auxiliary Space: $O(M+N)$

Constraints:

• $1<=M,N<=10^4$

String may contain duplicate characters.

Solution

Python

def UncommonChars(self, A, B):
    count_A = Counter(A)
    count_B = Counter(B)
    uncommon_chars = [
    for char in count_A:
        if char not in count_B:
            uncommon_chars.append(char)
    for char in count_B:
        if char not in count_A:
            uncommon_chars.append(char)
    uncommon_chars.sort()
    if not uncommon_chars:
        return "-1"
    else:
        return ''.join(uncommon_chars)

Java

String UncommonChars(String A, String B) {
    Set<Character> setA = new HashSet<>();
    Set<Character> setB = new HashSet<>();
    for (char ch : A.toCharArray()) {
        setA.add(ch);
    }
    for (char ch : B.toCharArray()) {
        setB.add(ch);
    Set<Character> uniqueChars = new HashSet<>();
    for (char ch : setA) {
        if (!setB.contains(ch)) {
            uniqueChars.add(ch);
        }
    }
    for (char ch : setB) {
        if (!setA.contains(ch)) {
            uniqueChars.add(ch);
        }
    }
    List<Character> sortedList = new ArrayList<>(uniqueChars);
    Collections.sort(sortedList);
    StringBuilder builder = new StringBuilder();
    for (char ch : sortedList) {
        builder.append(ch);
    }
    String result = builder.toString();
    if (result.isEmpty()) {
        return "-1";
    }
    return result;
}

C++

string UncommonChars(string A, string B) {
    unordered_set<char> setA;
    unordered_set<char> setB;
    for (char ch : A) {
        setA.insert(ch);
    for (char ch : B) {
        setB.insert(ch);
    } 
    unordered_set<char> uniqueChars;
    for (char ch : setA) {
        if (setB.find(ch) == setB.end()) {
            uniqueChars.insert(ch);
        }
    }
    for (char ch : setB) {
        if (setA.find(ch) == setA.end()) {
            uniqueChars.insert(ch);
        }
    }
    vector<char> sortedList(uniqueChars.begin(), uniqueChars.end());
    sort(sortedList.begin(), sortedList.end());
    string result(sortedList.begin(), sortedList.end());
    if (result.empty()) {
        return "-1";
    }
    return result;
}

C

char* UncommonChars(const char* A, const char* B) {
    int map[26] = {0};
    for (int i = 0; A[i] != '\0'; ++i) {
        map[A[i] - 'a'] = 1;
    }
    for (int i = 0; B[i] != '\0'; ++i) {
        if (map[B[i] - 'a'] == 1 || map[B[i] - 'a'] == -1) {
            map[B[i] - 'a'] = -1;
        } else {
            map[B[i] - 'a'] = 2;
        }
    }
    char* result = (char*)malloc(27 * sizeof(char));
    int index = 0;
    for (int i = 0; i < 26; ++i) {
        if (map[i] > 0) {
            result[index++] = 'a' + i;
        }
    }
    result[index] = '\0';
    if (index == 0) {
        free(result);
        result = (char*)malloc(3 * sizeof(char)); 
        strcpy(result, "-1");
    }
    return result;
}

• Time Complexity: $O(M+N)$
• Auxiliary Space: $O(M+N)$