Java O(n) Easy To Understand, Optimal Solution O(1) Space


  • 0
    B

    Explanation
    There are many ways to do this question that involve sorting or using a dictionary, but I will show you the optimal solution that runs strictly in O(n) with O(1) space.

    The idea to this solution is to take advantage of ASCII codes. First, we sum up the ASCII codes of all characters in t. Then, we subtract the ASCII codes of all characters in s from t's sum. The remaining value is the ASCII code for the newly added character.

    Time Complexity
    The time complexity to my solution is O(n) where n is the number of characters in input t, since scanning through t runs in O(n) and s runs in O(n-1): O(n) + O(n-1) = O(n).

    class Solution {
        public char findTheDifference(String s, String t) {
            int sum = 0;
            for (int i = 0; i < t.length(); i++) {
                sum += (int) t.charAt(i);
            }
            for (int i = 0; i < s.length(); i++) {
                sum -= (int) s.charAt(i);
            }
            return (char) sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.