Uncommon Characters Between Two Strings

Given two strings, s1 and s2, find all characters that are present in either of the two strings but not in both. Return the uncommon characters as a string in alphabetical order.

Input/Output Examples

plaintext
Example 1:
Input:
s1 = "characters"
s2 = "alphabets"
Output: "bchlpr"
Explanation: Characters that are unique to each string are "bchlpr".

Example 2:
Input:
s1 = "apple"
s2 = "peach"
Output: "achl"
Explanation: Characters unique to each string are "achl".

Example 3:
Input:
s1 = "hello"
s2 = "world"
Output: "dehrw"
Explanation: Characters unique to each string are "dehrw".

Approach to Find Uncommon Characters Between Two Strings

  1. Use Frequency Counters for Both Strings:
    • Initialize two arrays (or hash maps) to count the frequency of each character in both s1 and s2.
  2. Identify Uncommon Characters:
    • Traverse through all possible characters and check if a character is present in only one of the two strings.
    • If the character is unique to one string, add it to the result.
  3. Sort the Result:
    • Store the uncommon characters in a list, sort them alphabetically, and then return as a single string.

C++ Program to Find Uncommon Characters Between Two Strings

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find uncommon characters between two strings
string uncommonCharacters(const string& s1, const string& s2) {
    vector<int> freq1(26, 0), freq2(26, 0);
    
    for (char c : s1) freq1[c - 'a'] = 1;
    for (char c : s2) freq2[c - 'a'] = 1;

    string result;
    for (int i = 0; i < 26; i++) {
        if ((freq1[i] && !freq2[i]) || (!freq1[i] && freq2[i])) {
            result += (i + 'a');
        }
    }
    
    return result;
}

int main() {
    string s1 = "characters";
    string s2 = "alphabets";
    cout << "Uncommon characters: " << uncommonCharacters(s1, s2) << endl;
    return 0;
}

Java Program to Find Uncommon Characters Between Two Strings

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class UncommonCharacters {

    // Function to find uncommon characters between two strings
    public static String uncommonCharacters(String s1, String s2) {
        boolean[] freq1 = new boolean[26];
        boolean[] freq2 = new boolean[26];

        for (char c : s1.toCharArray()) freq1[c - 'a'] = true;
        for (char c : s2.toCharArray()) freq2[c - 'a'] = true;

        List<Character> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if ((freq1[i] && !freq2[i]) || (!freq1[i] && freq2[i])) {
                result.add((char)(i + 'a'));
            }
        }

        Collections.sort(result);
        StringBuilder sb = new StringBuilder();
        for (char c : result) sb.append(c);
        return sb.toString();
    }

    public static void main(String[] args) {
        String s1 = "apple";
        String s2 = "peach";
        System.out.println("Uncommon characters: " + uncommonCharacters(s1, s2));
    }
}

Python Program to Find Uncommon Characters Between Two Strings

python
# Function to find uncommon characters between two strings
def uncommon_characters(s1, s2):
    freq1 = set(s1)
    freq2 = set(s2)

    uncommon = (freq1 - freq2) | (freq2 - freq1)
    return ''.join(sorted(uncommon))

# Example usage
if __name__ == "__main__":
    s1 = "hello"
    s2 = "world"
    print("Uncommon characters:", uncommon_characters(s1, s2))
  • Time Complexity: O(n + m + 26 log 26), where n and m are the lengths of s1 and s2, respectively. The sorting of a fixed 26-character alphabet takes constant time, making this efficient for English lowercase letters.
  • Space Complexity: O(1), as the character set is limited (assuming lowercase English letters), and the frequency counters are fixed in size.

DSA

2145

820

Related Articles