Skip to content

389. Find the Difference

Description

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"

 

Constraints:

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s and t consist of lowercase English letters.

Solutions

Solution 1: Counting

Thinking

\(t\) is \(s\) shuffled plus one letter. A count difference finds it.

Count \(s\), decrement along \(t\); the first negative frequency is the extra letter.

We can use a hash table or array \(cnt\) to count the occurrence of each character in string \(s\), then traverse string \(t\). For each character, we subtract its occurrence in \(cnt\). If the corresponding count is negative, it means that the occurrence of this character in \(t\) is greater than in \(s\), so this character is the added character.

The time complexity is \(O(n)\), and the space complexity is \(O(|\Sigma|)\), where \(n\) is the length of the string, and \(\Sigma\) represents the character set. Here the character set is all lowercase letters, so \(|\Sigma|=26\).

1
2
3
4
5
6
7
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
            if cnt[c] < 0:
                return c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int i = 0;; ++i) {
            if (--cnt[t.charAt(i) - 'a'] < 0) {
                return t.charAt(i);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    char findTheDifference(string s, string t) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        for (char& c : t) {
            if (--cnt[c - 'a'] < 0) {
                return c;
            }
        }
        return ' ';
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func findTheDifference(s, t string) byte {
    cnt := [26]int{}
    for _, ch := range s {
        cnt[ch-'a']++
    }
    for i := 0; ; i++ {
        ch := t[i]
        cnt[ch-'a']--
        if cnt[ch-'a'] < 0 {
            return ch
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function findTheDifference(s: string, t: string): string {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    for (const c of t) {
        --cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    for (let i = 0; ; ++i) {
        if (cnt[i] < 0) {
            return String.fromCharCode(i + 'a'.charCodeAt(0));
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let n = s.len();
        let mut count = [0; 26];
        for i in 0..n {
            count[(s[i] - b'a') as usize] += 1;
            count[(t[i] - b'a') as usize] -= 1;
        }
        count[(t[n] - b'a') as usize] -= 1;
        char::from(b'a' + (count.iter().position(|&v| v != 0).unwrap() as u8))
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
char findTheDifference(char* s, char* t) {
    int n = strlen(s);
    int cnt[26] = {0};
    for (int i = 0; i < n; i++) {
        cnt[s[i] - 'a']++;
        cnt[t[i] - 'a']--;
    }
    cnt[t[n] - 'a']--;
    for (int i = 0;; i++) {
        if (cnt[i]) {
            return 'a' + i;
        }
    }
}

Solution 2: Summation

Thinking

Counting uses \(O(\Sigma)\) space. The difference of ASCII sums is the extra code point, in \(O(1)\) space.

We can sum the ASCII values of each character in string \(t\), then subtract the sum of the ASCII values of each character in string \(s\). The final result is the ASCII value of the added character.

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

1
2
3
4
5
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        a = sum(ord(c) for c in s)
        b = sum(ord(c) for c in t)
        return chr(b - a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public char findTheDifference(String s, String t) {
        int ss = 0;
        for (int i = 0; i < t.length(); ++i) {
            ss += t.charAt(i);
        }
        for (int i = 0; i < s.length(); ++i) {
            ss -= s.charAt(i);
        }
        return (char) ss;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int a = 0, b = 0;
        for (char& c : s) {
            a += c;
        }
        for (char& c : t) {
            b += c;
        }
        return b - a;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func findTheDifference(s string, t string) byte {
    ss := 0
    for _, c := range s {
        ss -= int(c)
    }
    for _, c := range t {
        ss += int(c)
    }
    return byte(ss)
}

1
2
3
4
5
6
function findTheDifference(s: string, t: string): string {
    return String.fromCharCode(
        [...t].reduce((r, v) => r + v.charCodeAt(0), 0) -
            [...s].reduce((r, v) => r + v.charCodeAt(0), 0),
    );
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let mut ans = 0;
        for c in s.as_bytes() {
            ans ^= c;
        }
        for c in t.as_bytes() {
            ans ^= c;
        }
        char::from(ans)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
char findTheDifference(char* s, char* t) {
    int n = strlen(s);
    char ans = 0;
    for (int i = 0; i < n; i++) {
        ans ^= s[i];
        ans ^= t[i];
    }
    ans ^= t[n];
    return ans;
}

Comments