C/C++ Find the Difference of Two Lowercase Strings

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Example 1:
Input: s = “abcd”, t = “abcde”
Output: “e”
Explanation: ‘e’ is the letter that was added.

Example 2:
Input: s = “”, t = “y”
Output: “y”

Example 3:
Input: s = “a”, t = “aa”
Output: “a”

Example 4:
Input: s = “ae”, t = “aea”
Output: “a”

Constraints:
0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lower-case English letters.

Find the Difference of Two Lowercase Strings Using unordered_map

Let’s keep the counter for each lowercase in the STL::unordered_map (hash table), and the second scan for the target string t is to decrement the counter until negative counter which means it is the additional letter desired.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char, int> map;
        for (char c:s) {
            if (map.count(c)) {
                map[c] ++;
            } else {
                map[c] = 1;
            }
        }
        for (char c:t) {
            if (map.count(c)) {
                map[c] --;
                if (map[c] < 0) {
                    return c;
                }
            } else {
                return c;
            }
        }
        return 0; // undefined.
    }
};

class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char, int> map;
        for (char c:s) {
            if (map.count(c)) {
                map[c] ++;
            } else {
                map[c] = 1;
            }
        }
        for (char c:t) {
            if (map.count(c)) {
                map[c] --;
                if (map[c] < 0) {
                    return c;
                }
            } else {
                return c;
            }
        }
        return 0; // undefined.
    }
};

Find the Difference of Two Lowercase Strings using Static Array of Counters

The puzzle explicity says the input strings are both lowercase letters. So we can declare a static array initialized to zero (26 elements). This makes the program shorter and concise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    char findTheDifference(string s, string t) {
        int map[26] = {0};
        for (char c:s) {
            map[c-97] ++;
        }
        for (char c:t) {
            if (map[c-97] == 0) {
                return c;
            }
            map[c-97]--;
        }
        return 0; // undefined.
    }
};

class Solution {
public:
    char findTheDifference(string s, string t) {
        int map[26] = {0};
        for (char c:s) {
            map[c-97] ++;
        }
        for (char c:t) {
            if (map[c-97] == 0) {
                return c;
            }
            map[c-97]--;
        }
        return 0; // undefined.
    }
};

Both methods pass all the tests quite efficiently (both O(n) time complexity, the first approach using unordered_map has O(n) space complexity while the second approach has O(1) space complexity). The first approach is more flexible since it does not require the strings contain only the lowercase letters.

See also: Teaching Kids Programming – Find the Difference of Two Almost Same Strings

–EOF (The Ultimate Computing & Technology Blog) —