Scale Engineer

Find the Difference

Easy
#0376Time: O(N log N), where N is the length of the string `t`. The dominant operation is sorting the character arrays.Space: 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).
Patterns
Bit Manipulation
Algorithms
Sorting
Data structures
Hash TableString

Prompt

[Fetch error]

Approaches

4 approaches with complexity analysis and trade-offs.

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].

Walkthrough

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

Time

O(N log N), where N is the length of the string `t`. The dominant operation is sorting the character arrays.

Space

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).

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem