Find the Difference

EASY

Description

[Fetch error]

Approaches

Checkout 4 different approaches to solve Find the Difference. Click on different approaches to view the approach and algorithm in detail.

Brute Force using Sorting

This approach relies on sorting. If we sort the characters of both strings, they will be identical up to the length of the original string s. By comparing the sorted strings character by character, the first mismatch we find will reveal the extra letter added to t. If all characters match up to the end of s, the extra character must be the very last character of the sorted t.

Algorithm

Convert both strings s and t into character arrays, let's call them sChars and tChars.
Sort both sChars and tChars alphabetically.
Iterate from the first character up to the length of s.
In each iteration, compare sChars[i] with tChars[i].
If the characters at the current index i are different, tChars[i] is the added character, so return it.
If the loop completes without finding any difference, it means the extra character is the last character in tChars. Return tChars[t.length() - 1].

The core idea is that after sorting, two identical sets of characters would result in identical arrays. Since t has one extra character, its sorted version will be identical to s's sorted version until the point where the extra character is positioned, or the extra character will be appended at the end.

import java.util.Arrays;

class Solution {
    public char findTheDifference(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        Arrays.sort(sChars);
        Arrays.sort(tChars);

        for (int i = 0; i < sChars.length; i++) {
            if (sChars[i] != tChars[i]) {
                return tChars[i];
            }
        }

        // If the loop finishes, the extra character is the last one in t
        return tChars[tChars.length - 1];
    }
}

Complexity Analysis

Time Complexity: O(N log N), where N is the length of the string `t`. The dominant operation is sorting the character arrays.Space Complexity: O(N), where N is the length of the string `t`. This space is required to store the character arrays for sorting. Some sorting algorithms might use additional space (e.g., `O(log N)` for quicksort's recursion stack).

Pros and Cons

Pros:

The logic is straightforward and easy to understand.

Cons:

The time complexity of O(N log N) is suboptimal for this problem.
It requires extra space to hold the character arrays, which can be O(N).

Code Solutions

Checking out 3 solutions in different languages for Find the Difference. Click on different languages to view the code.

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 ); } } } }

Video Solution

Watch the video walkthrough for Find the Difference

Algorithms:

Sorting

Patterns:

Bit Manipulation

Data Structures:

Hash TableString