389-find-the-difference

Try it on leetcode

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.

Solution(Python)

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return self.charCode(s, t)

    """
    Run Two loops check all possible chars from t in s to find odd one 
    Time Complexity: O(n^2)
    Space Comnplexity: O(1)
    """

    def bruteforce(self, s: str, t: str) -> str:
        for ch in t:
            if ch not in s:
                return ch

    """
    create Hashfrequency table of chars of t  and decrement their resepective frequency for each character in s
    
    atlast the character with frequency 1 is the result
    
    Time Complexity: O(n)
    Space Comnplexity: O(n)
    """

    def hashtable(self, s: str, t: str) -> str:
        Hastable = defaultdict(lambda: 0)

        for ch in t:
            Hastable[ch] += 1

        for ch in s:
            Hastable[ch] -= 1

        for ch in Hastable:
            if Hastable[ch] == 1:
                return ch

    """
    since input consists of only small alphabets we could use counting sort to sort the two strings and find the odd element in  sorted strings
    
    This Idea is similar to the Hashtable and performance wise they are still same
    
    
    Time Complexity: O(n)
    Space Comnplexity: O(n)
    """

    def sorting(self, s: str, t: str) -> str:
        def countingsort(s):
            sortedList = [0] * 26

            for ch in s:
                sortedList[ord(ch) - ord("a")] += 1

            res = []

            for i in range(26):
                for times in range(sortedList[i]):
                    res.append(chr(sortedList[i] + ord("a")))
            return "".join(s)

        s = countingsort(s)
        t = countingsort(t)

        for i in range(len(s)):
            if s[i] != t[i]:
                return s[i]
        return t[-1]

    """
    xor of all characters in ordinal form form both s and t gives the result
    because xor cancels the pair of same number only the additional number will be left out

    
    
    Time Complexity: O(n)
    Space Comnplexity: O(1)
    """

    def bitmanipul(self, s: str, t: str) -> str:
        res = 0

        for ch in s:
            res ^= ord(ch)
        for ch in t:
            res ^= ord(ch)
        return chr(res)

    """
    Summate character code of all characters in s and in t separately and their difference is the character code of our result char
    

    Time Complexity: O(n)
    Space Comnplexity: O(1)
    """

    def charCode(self, s: str, t: str) -> str:
        s_sum = sum([ord(ch) for ch in s])
        t_sum = sum([ord(ch) for ch in t])
        return chr(t_sum - s_sum)