Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0389 - Find the Difference
    0389 - Find the Difference
    0389 - Find the Difference
    0389 - Find the Difference

    0389 - Find the Difference

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/find-the-difference/

    Solution 1 - Counter Approach

    Given two strings s and t, where t is generated by randomly shuffling s and adding one extra letter, find the added letter. Count character frequencies in s using a dictionary, then iterate through t decrementing counts. The character whose count goes below zero is the added letter.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - XOR Approach

    XOR all characters in both strings together. Since every character in s appears in t, they cancel out, leaving only the added character. This works because a ^ a = 0 and a ^ 0 = a.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 3 - ASCII Sum Approach

    Sum the ASCII values of all characters in both strings. The difference between the sum of t and the sum of s gives the ASCII value of the added character.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0389.1 - Find the Difference - Solution 1 - Counter Approach """

#####################################################################################
# Imports
#####################################################################################
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findTheDifference(self, s: str, t: str) -> str:
        """Find the Difference Function"""
        count = Counter(s)
        for char in t:
            if count[char] == 0:
                return char
            count[char] -= 1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findTheDifference("abcd", "abcde"))
    print(Solution().findTheDifference("", "y"))
    print(Solution().findTheDifference("a", "aa"))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0389.2 - Find the Difference - Solution 2 - XOR Approach """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findTheDifference(self, s: str, t: str) -> str:
        """Find the Difference Function"""
        result = 0
        for char in s:
            result ^= ord(char)
        for char in t:
            result ^= ord(char)
        return chr(result)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findTheDifference("abcd", "abcde"))
    print(Solution().findTheDifference("", "y"))
    print(Solution().findTheDifference("a", "aa"))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0389.3 - Find the Difference - Solution 3 - ASCII Sum Approach """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findTheDifference(self, s: str, t: str) -> str:
        """Find the Difference Function"""
        return chr(sum(ord(c) for c in t) - sum(ord(c) for c in s))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findTheDifference("abcd", "abcde"))
    print(Solution().findTheDifference("", "y"))
    print(Solution().findTheDifference("a", "aa"))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()